pith. sign in

arxiv: 2606.15761 · v3 · pith:KRT2K3RRnew · submitted 2026-06-14 · 🧮 math.CO · cs.DM

Sharp bounds between the saturation number and the harmonic index

Chakshu Gupta This is my paper

Pith reviewed 2026-06-27 03:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords saturation numberharmonic indextreesmaximal matchinggraph boundsconjecture counterexamplesTxGraffiti
0
0 comments X

The pith

Every nontrivial tree T satisfies μ*(T) < 3/2 H(T), with the constant 3/2 best possible.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves sharp inequalities relating the saturation number, the smallest size of a maximal matching, to the harmonic index, which sums 2 over the degree sum for each edge. For any nontrivial tree, the saturation number is always less than three-halves the harmonic index, and this factor is the best possible as the ratio can get arbitrarily close. A matching upper bound shows that the harmonic index is less than four times the saturation number in any graph with at least one edge. Together these pin the saturation number for trees between one quarter and three halves of the harmonic index. This refines a refuted conjecture that the saturation number never exceeds the harmonic index, while providing practical bounds since the harmonic index is easy to compute.

Core claim

Restricting attention to trees yields the sharp bounds μ*(T) < (3/2) H(T) for every nontrivial tree T, with the constant best possible as shown by certain families, and the complementary H(G) < 4 μ*(G) for every graph G with an edge. Consequently, on nontrivial trees one has (1/4) H(T) < μ*(T) < (3/2) H(T), with both constants best possible. The friendship graph on nine vertices is the smallest counterexample to the TxGraffiti conjecture μ* ≤ H, while the smallest tree counterexample is the subdivided star on eleven vertices. For each m, there exist graphs with m hubs whose ratio μ*/H approaches m+1, but the conjecture holds for regular graphs.

What carries the argument

The saturation number μ* as the minimum cardinality of a maximal matching, compared against the harmonic index H defined as the sum over edges of 2/(d(u)+d(v)), with the ratio bounds obtained by analyzing the structure of maximal matchings and vertex degrees in trees.

Load-bearing premise

The standard definitions of the saturation number as the size of the smallest maximal matching and the harmonic index as the edge sum of 2 over degree sums remain valid for the finite simple connected graphs considered.

What would settle it

Discovery of a nontrivial tree T where μ*(T) is at least 3/2 times H(T), or a graph with an edge where H(G) is at least 4 times μ*(G).

Figures

Figures reproduced from arXiv: 2606.15761 by Chakshu Gupta.

Figure 1
Figure 1. Figure 1: The join of a disjoint union of edges with an independent set, drawn for two edges and [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The subdivided star S5 on eleven vertices, a tree counterexample with µ ∗ = 5 > 100/21 = H. Being acyclic, it contains no triangle. One leg is labelled with its middle vertex m1 and leaf ℓ1. Theorem 1 (Subdivided star). For the subdivided star Sk (k ≥ 1), µ ∗ (Sk) = k and H(Sk) = 2k k + 2 + 2k 3 . Consequently µ ∗ (Sk) ≤ H(Sk) if and only if k ≤ 4, with equality at k = 4 (S4, nine vertices), and µ ∗ (Sk)/H… view at source ↗
Figure 3
Figure 3. Figure 3: The friendship graph F4, a smallest counterexample, on nine vertices, formed by four triangles sharing a single hub z, giving µ ∗ = 4 > 18/5 = H. The shaded triangle is one rim pair a1b1 with the hub. Theorem 3 (Saturation number and harmonic index of Fk). For the friendship graph Fk (k ≥ 1), µ ∗ (Fk) = k and H(Fk) = 2k k + 1 + k 2 . Consequently, µ ∗ (Fk) ≤ H(Fk) if and only if k ≤ 3, with equality at k =… view at source ↗
Figure 4
Figure 4. Figure 4: The generalized windmill G2,3 with m = 2 and k = 3. Two independent hubs z1, z2, each joined to all 2k = 6 blade vertices, with a perfect matching pairing the blades into k = 3 edges (thick). The shaded blade together with the two hubs forms K4 minus the hub edge. The case m = 1 is shown in [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
read the original abstract

The saturation number $\mu^*(G)$ of a graph $G$ is the minimum cardinality of a maximal matching, and $H(G)$ is its harmonic index. TxGraffiti conjectured in 2023 that $\mu^*(G) \le H(G)$ for every nontrivial connected graph $G$, and B{\i}y{\i}ko\u{g}lu refuted this by showing that the ratio $\mu^*(G)/H(G)$ can be made arbitrarily large. Restricting to trees bounds the ratio sharply. Every nontrivial tree $T$ satisfies $\mu^*(T) < \frac{3}{2} H(T)$, with the constant $3/2$ best possible. A complementary bound $H(G) < 4\mu^*(G)$ holds for every graph with an edge, so on a nontrivial tree the saturation number is pinned to $\frac{1}{4} H(T) < \mu^*(T) < \frac{3}{2} H(T)$, both constants best possible. The friendship graph $F_4$ is a smallest counterexample to the conjecture, on nine vertices, and the smallest tree counterexample is the subdivided star on eleven vertices. For each positive integer $m$ a family of graphs with $m$ hubs has ratio approaching $m+1$, while the conjecture holds whenever all vertices have equal degree. Both invariants arise in applications, the harmonic index as a molecular descriptor and the saturation number as a measure of adsorption inefficiency, and the bounds estimate the latter, which is NP-hard to compute, by the former, which is computable in linear time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper refutes the TxGraffiti conjecture μ*(G) ≤ H(G) for nontrivial connected graphs by exhibiting families where the ratio μ*/H becomes arbitrarily large, but restricts to trees to obtain sharp bounds: every nontrivial tree T satisfies 1/4 H(T) < μ*(T) < 3/2 H(T), with both constants best possible. It identifies the friendship graph F4 (nine vertices) as the smallest counterexample and the subdivided star on eleven vertices as the smallest tree counterexample, and shows that the conjecture holds when all degrees are equal. Complementary results include H(G) < 4μ*(G) for any graph with an edge and families with m hubs where the ratio approaches m+1.

Significance. The sharp constants and explicit extremal constructions (friendship graphs, subdivided stars, m-hub families) provide concrete, falsifiable bounds that estimate the NP-hard saturation number via the linear-time harmonic index. This is useful for applications in molecular descriptors and adsorption inefficiency. The work resolves a recent conjecture with both negative (arbitrarily large ratio) and positive (pinned interval for trees) results, and the parameter-free nature of the statements is a strength.

major comments (2)
  1. [Abstract] The abstract asserts the bounds μ*(T) < (3/2) H(T) and H(G) < 4μ*(G) together with sharpness via explicit families, but supplies no derivation steps, error analysis, or verification that the constants are achieved; the central claim therefore rests on uninspectable proofs.
  2. [Counterexample section] The claim that the subdivided star on eleven vertices is the smallest tree counterexample and achieves a ratio arbitrarily close to 3/2 requires an explicit computation of both μ* and H for that graph (and the limit family) to confirm it is load-bearing for sharpness.
minor comments (2)
  1. [Introduction] Notation for the saturation number is introduced as μ*(G) but the definition of a maximal matching should be recalled explicitly for readers outside the area.
  2. [Equal-degree case] The statement that the conjecture holds 'whenever all vertices have equal degree' should include a short proof or reference to the relevant theorem number.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for their positive evaluation of its significance. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] The abstract asserts the bounds μ*(T) < (3/2) H(T) and H(G) < 4μ*(G) together with sharpness via explicit families, but supplies no derivation steps, error analysis, or verification that the constants are achieved; the central claim therefore rests on uninspectable proofs.

    Authors: Abstracts in mathematical papers are concise overviews and typically omit detailed derivations and error analyses, which are reserved for the main text. The derivations of the bounds, the verification that the constants are sharp through explicit constructions, and all supporting calculations are provided in full in Sections 3 and 4 of the manuscript. The proofs are therefore inspectable from the complete document. revision: no

  2. Referee: [Counterexample section] The claim that the subdivided star on eleven vertices is the smallest tree counterexample and achieves a ratio arbitrarily close to 3/2 requires an explicit computation of both μ* and H for that graph (and the limit family) to confirm it is load-bearing for sharpness.

    Authors: We concur that explicit computations are valuable for confirming the sharpness. The manuscript already specifies the subdivided star on eleven vertices as the smallest tree counterexample and provides the necessary computations of μ* and H to establish the ratio. For the limit family, the asymptotic analysis shows the ratio approaching 3/2. To further address the referee's concern, we will revise the counterexample section to present these computations in greater detail, including a step-by-step breakdown for the eleven-vertex graph and the limiting case. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes sharp inequalities between the saturation number μ*(T) and harmonic index H(T) for trees via direct proofs on finite simple graphs, using standard definitions of maximal matchings and the harmonic index sum. Sharpness is witnessed by explicit extremal families (friendship graphs, subdivided stars, m-hub constructions) rather than any fitted parameters, self-definitional equations, or load-bearing self-citations. The central claims reduce to combinatorial arguments on graph invariants without reduction to inputs by construction. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definitions of graphs, trees, matchings, saturation number, and harmonic index; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of finite simple connected graphs, maximal matchings, and the harmonic index sum hold without modification.
    These definitions are invoked to state μ* and H and to formulate the conjecture and bounds.

pith-pipeline@v0.9.1-grok · 5817 in / 1243 out tokens · 69892 ms · 2026-06-27T03:53:10.860193+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

  1. [1]

    Saturation number of a graph

    Mohammad Bagher Ahmadi and Vahid Amiri Khorasani. Saturation number of a graph. In Ivan Gutman, Boris Furtula, Kinkar Chandra Das, Emina Milovanovi\' c , and Igor Milovanovi\' c , editors, Bounds in Chemical Graph Theory -- Advances , number 21 in Mathematical Chemistry Monographs, pages 217--232. University of Kragujevac, Kragujevac, 2017

    2017

  2. [2]

    On the saturation number of graphs

    Saeid Alikhani and Neda Soltani. On the saturation number of graphs. Iranian J. Math. Chem. , 9(4):289--299, 2018

    2018

  3. [3]

    Harmonic index and its generalizations: Extremal results and bounds

    Akbar Ali, Lingping Zhong, and Ivan Gutman. Harmonic index and its generalizations: Extremal results and bounds. MATCH Commun. Math. Comput. Chem. , 81(2):249--311, 2019

    2019

  4. [4]

    A note on the TxGraffiti conjecture about harmonic index and minimum maximal matching number

    T\" u rker B y ko g lu. A note on the TxGraffiti conjecture about harmonic index and minimum maximal matching number. MATCH Commun. Math. Comput. Chem. , 96(3):1097--1099, 2026

    2026

  5. [5]

    Automated conjecturing with TxGraffiti

    Randy Davila. Automated conjecturing with TxGraffiti . Annals of Mathematics and Artificial Intelligence , 2026

    2026

  6. [6]

    In reverie together: Ten years of mathematical discovery with a machine collaborator

    Randy Davila, Boris Brimkov, and Ryan Pepper. In reverie together: Ten years of mathematical discovery with a machine collaborator. arXiv preprint arXiv:2507.17780 , 2025

    arXiv 2025

  7. [7]

    On conjectures of Graffiti --- II

    Siemion Fajtlowicz. On conjectures of Graffiti --- II . In Congr. Numer. , volume 60, pages 187--197, 1987

    1987

  8. [8]

    On conjectures of Graffiti

    Siemion Fajtlowicz. On conjectures of Graffiti . Discrete Math. , 72(1--3):113--118, 1988

    1988

  9. [9]

    Note on the harmonic index of a graph

    Aleksandar Ili\' c . Note on the harmonic index of a graph. arXiv preprint arXiv:1204.3313 , 2012

    Pith/arXiv arXiv 2012

  10. [10]

    On the harmonic index and the matching number of a tree

    Jian-Bo Lv and Jianxi Li. On the harmonic index and the matching number of a tree. Ars Combin. , 116:407--416, 2014

    2014

  11. [11]

    The harmonic index of unicyclic graphs with given matching number

    Jian-Bo Lv, Jianxi Li, and Wai Chee Shiu. The harmonic index of unicyclic graphs with given matching number. Kragujevac J. Math. , 38(1):173--183, 2014

    2014

  12. [12]

    McKay and Adolfo Piperno

    Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II . J. Symbolic Comput. , 60:94--112, 2014

    2014

  13. [13]

    David P. Sumner. Randomly matchable graphs. J. Graph Theory , 3(2):183--186, 1979

    1979

  14. [14]

    Smallest maximal matchings of graphs

    Mostafa Tavakoli and Tomislav Do s li\' c . Smallest maximal matchings of graphs. Hacet. J. Math. Stat. , 52(2):356--366, 2023

    2023

  15. [15]

    General approach for obtaining extremal results on degree-based indices illustrated on the general sum-connectivity index

    Tom\' a s Vetr\' i k. General approach for obtaining extremal results on degree-based indices illustrated on the general sum-connectivity index. Electron. J. Graph Theory Appl. , 11(1):125--133, 2023

    2023

  16. [16]

    The harmonic index for graphs

    Lingping Zhong. The harmonic index for graphs. Appl. Math. Lett. , 25(3):561--566, 2012

    2012