Maximum graphs with a unique minimum dominating set (Q1861257): Difference between revisions

This note states a conjecture concerning the maximum number of edges in a graph that has a unique minimum dominating set. Let \(m(n,\gamma)\) be the maximum number of edges of a graph \(G\) of order \(n\) without isolated vertices that has a unique dominating set of cardinality \(\gamma \geq 1\). For \(n \geq 3 \gamma\) the authors conjecture that \(m(n,\gamma) = {n \choose 2}-\lceil {n-1 \over 2} \rceil\) for \(\gamma =1\) and \(m(n,\gamma) = {n \choose 2}- \gamma \left( n+ {\gamma-5 \over 2} \right) = {n-\gamma\choose 2}-\gamma(\gamma-2)\) for \(\gamma \geq 2\). The authors construct extremal graphs, showing that \(m(n,\gamma)\) is at least as large as stated in the conjecture. Furthermore they prove the conjecture for the special cases of \(\gamma=1\) and of \(n=3\gamma\). Finally, they prove the conjecture for the special case of graphs having a certain additional technical property.