{"id":"arxiv/2606.15761","url":"https://arxiv.org/abs/2606.15761","tags":["math.CO","cs.DM"],"score":0,"title":"Sharp bounds between the saturation number and the harmonic index","domain":"math.CO","source":"arxiv","authors":["Chakshu Gupta"],"reviews":0,"subject":"math.CO","summary":"The saturation number $μ^*(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 $μ^*(G) \\le H(G)$ for every nontrivial connected graph $G$, and Bıyıkoğlu refuted this by showing that the ratio $μ^*(G)/H(G)$ can be made arbitrarily large. Restricting to trees bounds the ratio sharply. Every nontrivial tree $T$ satisfies $μ^*(T) < \\frac{3}{2} H(T)$, with the constant $3/2$ best possible. A complementary bound $H(G) < 4μ^*(G)$ holds for every graph with an edge, so on a nontrivial tree the saturation number is…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-14","reactions":{}}