Independence and connectivity in 3-domination-critical graphs (Q1861215): Difference between revisions

Let \(G\) be a finite undirected simple graph. A set of vertices \(S\) is called a dominating set of \(G\), if all vertices of \(G\) are either elements or neighbours of elements of \(S\). The domination number \(\gamma\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A graph is called \(3\)-domination-critical, if it has domination number \(3\) and every addition of an edge yields a graph with domination number \(2\). Let \(G\) be connected and \(3\)-domination-critical and \(\delta\), \(\alpha\), \(\kappa\) be the minimum degree, the independence number, and the connectivity of \(G\), respectively. The authors prove that \(\alpha\leq \kappa+2\) and that if \(\alpha=\kappa+2\), then \(\kappa=\delta\). Furthermore, they give a short proof of a theorem by \textit{E. Wojcicka} [J. Graph Theory 14, 205-215 (1990; Zbl 0702.05058)] which states that if \(G\) is connected, \(3\)-critical and has at least \(7\) vertices, then \(G\) has a Hamilton path.