Maximum graphs with a unique minimum dominating set
type: Item
instance of: scholarly article
title: Maximum graphs with a unique minimum dominating set
zbMATH Open document ID: 1011.05042
DOI: 10.1016/S0012-365X(02)00670-2
author: Miranca Fischermann
author: Dieter Rautenbach
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2003-03-16T00:00:00Z
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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1882192
zbMATH Keywords: minimum dominating set
zbMATH Keywords: extremal graphs
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00670-2
OpenAlex ID: W2055860530
Recommended article: Q3565859
Recommended article: Q4863436
Recommended article: Graphs with unique minimum specified domination sets
Recommended article: Graphs with unique minimum vertex-edge dominating sets
Recommended article: Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
Recommended article: On maximum number of minimal dominating sets in graphs
Recommended article: Q4595237
Recommended article: Graphs with unique maximum independent sets
Recommended article: Graphs with unique minimum paired-dominating set.
Recommended article: Q5505800
description: scientific article; zbMATH DE number 1882192