Maximum graphs with a unique minimum dominating set

DOI10.1016/S0012-365X(02)00670-2MaRDI QIDQ1861257zbMATH OpenOpenAlexFDO

Authors Miranca Fischermann, Dieter Rautenbach, Lutz Volkmann

Publication date 16 March 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00670-2

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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.

Recommendations

Cited in

(12)

This page was built for publication: Maximum graphs with a unique minimum dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861257)