Sharp bounds between the saturation number and the harmonic index

Abstract

The saturation number $\hat{I}{¼}^{\ast }(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 $\hat{I}{¼}^{\ast }(G)\le H(G)$ for every nontrivial connected graph $G$, and Bıyıkoğlu refuted this by showing that the ratio $\hat{I}{¼}^{\ast }(G)/H(G)$ can be made arbitrarily large. Restricting to trees bounds the ratio sharply. Every nontrivial tree $T$ satisfies $\hat{I}{¼}^{\ast }(T)<\frac{3}{2}H(T)$, with the constant $3/2$ best possible. A complementary bound $H(G)<4\hat{I}{¼}^{\ast }(G)$ holds for every graph with an edge, so on a nontrivial tree the saturation number is pinned to $\frac{1}{4}H(T)<\hat{I}{¼}^{\ast }(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.

10 pages, 4 figures. Studies Conjecture 4 of arXiv:2507.17780 (a TxGraffiti conjecture, μ^*(G)<=H(G), first refuted by T. Bıyıkoğlu, MATCH Commun. Math. Comput. Chem. 96 (2026) 1097-1099; this paper gives the order-9 smallest counterexample and sharp two-sided bounds between the saturation number μ^* and the harmonic index H. Code: https://github.com/ChakshuGupta13/lab