Some properties of 3-domination-critical graphs (Q1301830): Difference between revisions

The authors consider graphs having minimum degree \(\delta\geq 2\) and being 3-\(\gamma\)-critical, which means that their domination number \(\gamma\) is 3 and adding any new edge decreases this number. \textit{E. Wojcicka} [J. Graph Theory 14, No. 2, 205-215 (1990; Zbl 0702.05058)] conjectured that such a graph, whenever connected, is Hamiltonian. In view of this conjecture, in this paper it is proved that these graphs of order \(n\) are 1-tough and have circumference at least \(n-1\), thus generalizing earlier results by \textit{Y. Xue} and \textit{Z. Chen} [J. Nanjing Univ., Nat. Sci. Ed. 27, No. Spec. Issue, 58-62 (1991; Zbl 0762.05075)] and by \textit{D. P. Sumner} [Discrete Math. 86, No. 1-3, 33-46 (1990; Zbl 0725.05049)]. A main step of the proof consists in showing that each longest cycle in a connected 3-\(\gamma\)-critical graph is a dominating cycle.