Graphs with least domination number three-fifths their order (Q1567273)

A vertex set \(S\subseteq V\) in a finite undirected graph \(G= (V,E)\) is a dominating set if every vertex of \(V\setminus S\) is adjacent to some vertex in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set in \(G\). For a vertex set \(U\) let \(G(U)\) denote the subgraph induced by \(U\). A dominating set \(D\) is a least dominating set if \(\gamma(G(D))\leq \gamma(G(S))\) for any dominating set \(S\). Let \(\gamma_l(G)\) denote the minimum cardinality of a least dominating set in \(G\). Favaron showed that \(\gamma_l(G)\leq 3n/5\) for every connected graph on \(n\geq 2\) vertices. In this paper, the graphs of order \(n\) are characterized which are edge-minimal with respect to satisfying \(G\) is connected and \(\gamma_l(G)= 3n/5\). Furthermore, a family of graphs \(G\) of order \(n\) is constructed that are not cycles and are edge-minimal with respect to satisfying \(G\) is connected, has minimum degree \(\geq 2\) and \(\gamma_l(G)= 3n/5\).