Answers are grounded in this paper and cite their sources.
The conjecture-generating program TxGraffiti proposed that i(G) ≤ μ∗(G) for every regular graph G of positive degree, where i(G) is the minimum size of a maximal independent set and μ∗(G) is the minimum size of a maximal matching. In this paper, we give a connected cubic graph G of order 50 with i(G) = 16 > 15 = μ∗(G). The graph is the clause–literal graph of an explicit (2, 2)-regular 3-CNF formula. A short counting argument determines μ∗(G), while an exact exhaustive test of all 3¹⁵ partial assignments proves the lower bound on i(G). Since G is connected, it also refutes the corresponding conjecture for connected regular graphs. We also bound the gap i(G) − μ∗(G) available from this construction and extend the construction to k-regular graphs for every k ≥ 3. Code and verification data: https://github.com/HirotadaIwane/independent-domination-counterexample
No takes yet. Share an insight, caveat, or question.
Hirotada Iwane (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: