Abstract:TxGraffiti conjectured in 2023 that every nontrivial connected graph $G$ satisfies $\mu^*(G) \le H(G)$, where $\mu^*(G)$ is the saturation number and $H(G)$ is the harmonic index. The conjecture is false: the friendship graph $F_4$ satisfies $\mu^*(F_4) = 4 > 18/5 = H(F_4)$, and an exhaustive enumeration confirms that nine vertices is the smallest order admitting a counterexample. A generalized windmill family shows that the ratio $\mu^*/H$ can be made arbitrarily large. The conjecture does hold for every graph in which all vertices have the same degree, in which case $H(G) = n/2$.
From: Chakshu Gupta [view email]
[v1]
Sun, 14 Jun 2026 11:46:02 UTC (5 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。