Maximum graphs with a unique minimum dominating set (Q1861257)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum graphs with a unique minimum dominating set |
scientific article |
Statements
Maximum graphs with a unique minimum dominating set (English)
0 references
16 March 2003
0 references
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.
0 references
minimum dominating set
0 references
extremal graphs
0 references