A Degree-Spread Bound Between Independent Domination and Minimum Maximal Matchings: A Conjecture

For a finite simple graph G, let i(G) be its independent domination number, let mu*(G) be the minimum cardinality of a maximal matching, and let Delta(G) and delta(G) be its maximum and minimum degrees. We conjecture that every connected nontrivial graph satisfies i(G)-mu*(G) <= Delta(G)-delta(G). For regular graphs this specializes to the open TxGraffiti conjecture i(G) <= mu*(G). The correction by degree spread is best possible: equality holds for every balanced double star. Connectedness and nontriviality are necessary. We report exhaustive verification for all 273,192 connected nonisomorphic graphs of orders 2 through 9, together with supplementary structured and random tests. These finite computations are evidence only and do not constitute a proof.