← All problems

Estrada–Mugnolo's Kirchhoff-index ordering conjecture for hubs-biased resistance distances

5 years old · traced to

Let GG be a connected graph. Write Rα=1(G)\mathcal{\mathcal{\mathscr{R}}_{\mathnormal{\alpha=1}}}(G) for the Kirchhoff index based on the hubs-repelling resistance distance, Rα=0(G)\mathcal{\mathcal{\mathscr{R}}}_{\alpha=0}(G) for the standard Kirchhoff index, and Rα=−1(G)\mathcal{\mathcal{\mathscr{R}}_{\mathnormal{\alpha=-1}}}(G) for the Kirchhoff index based on the hubs-attracting resistance distance.

Kirchhoff-index ordering conjecture. For α∈{−1,1}\alpha\in\{-1,1\},

Rα=1(G)≥Rα=0(G)≥Rα=−1(G),\mathcal{\mathcal{\mathscr{R}}_{\mathnormal{\alpha=1}}}(G)\geq\mathcal{\mathcal{\mathscr{R}}}_{\alpha=0}(G)\geq\mathcal{\mathcal{\mathscr{R}}_{\mathnormal{\alpha=-1}}}(G),

with equality if and only if GG is regular.

The conjecture was formulated after computational experiments on more than 12,000 connected graphs with 5≤n≤85\leq n\leq 8, and predicts that hubs-repelling navigation gives the largest Kirchhoff index while hubs-attracting navigation gives the smallest. Its general validity is left open in the source.

References
  1. Ernesto Estrada and Delio Mugnolo, “Hubs-biased resistance distances on graphs and networks”, arXiv:2101.07103 (2021).

Progress summary

Refreshed
Open · progress reported

A recent unverified submission claims the conjecture is false by giving a concrete graph where the predicted ordering reverses.

Estrada and Mugnolo proposed that hubs-repelling, standard, and hubs-attracting Kirchhoff indices satisfy R1(G)≥R0(G)≥R−1(G)\mathcal{R}_{1}(G)\geq\mathcal{R}_{0}(G)\geq\mathcal{R}_{-1}(G), with equality exactly for regular graphs.

Known results

Estrada and Mugnolo (2021) verified the ordering computationally for more than 12,00012{,}000 connected graphs with 5≤n≤85\leq n\leq 8; no general proof or counterexample was reported in the published source.

November 7, 2026 community counterexample claim

A submitted proof argues that a clique with a five-edge pendant path violates the conjecture, reporting R1=1696684/14035<370/3=R0\mathcal{R}_{1}=1696684/14035<370/3=\mathcal{R}_{0}. It also claims failure under a literal Moore–Penrose interpretation. The argument and its claimed scope are unverified.

Current status (as of November 2026): The conjecture remains unsettled; a community submission claims a counterexample, but that claim has not been independently verified.

Sources

Solutions 1

A clique with a five-edge tail reverses the hubs-biased Kirchhoff orderingSee full solutionHide full solution

Result and scope. Estrada-Mugnolo (J. Math. Anal. Appl. 507 (2022) 125728, arXiv:2101.07103) Conjecture 4.13 asserts R_1 >= R_0 >= R_-1 for hubs-biased Kirchhoff indices, with equality iff regular. The spectral index the authors computed (Lemma 4.6, n*tr of the group inverse) satisfies the ordering for all 12,103 connected graphs with 5<=n<=8 (independent review), but K6 with a pendant five-edge path has R_1 = 1696684/14035 < 370/3 = R_0. The literal Moore-Penrose reading (4.3) also fails there (515538204/7137235) and already fails at n=5, an uncredited source inconsistency.

Complete proof: A clique with a five-edge tail reverses the hubs-biased Kirchhoff ordering · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.