A Degree–Independent-Domination Bound for the Saturation Number: A Conjecture

This preprint proposes a conjectured upper bound for the saturation number of a finite, simple, connected, nontrivial graph G: s(G) <= ceil(Delta(G) i(G) / 2), where s(G) is the minimum cardinality of a maximal matching, Delta(G) is the maximum degree, and i(G) is the independent domination number. The proposed bound is sharp for complete graphs, while connectedness cannot be omitted. The conjecture was exhaustively verified for all 273,192 connected nonisomorphic graphs of orders 2 through 9. Supplementary random and regular-graph computations found no counterexample. These finite computations constitute experimental evidence only and do not provide a proof. The accompanying archive contains the LaTeX source prepared for submission to arXiv. Code, tests, and machine-readable results are available from the related GitHub repository.