Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\) (Q1283070)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\) |
scientific article |
Statements
Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\) (English)
0 references
7 July 1999
0 references
Let \(\delta, \gamma\) and \(\alpha\) be respectively the minimum degree, the domination number and the independence number of a graph \(G\). The graph \(G\) is 3-\(\gamma\)-critical if \(\gamma = 3\) and the addition of any edge decreases \(\gamma\) by 1. It was conjectured that any connected 3-\(\gamma\)-critical graph with \(\delta \geq 2\) is Hamiltonian. In \textit{O. Faravon, F. Tian} and \textit{L. Zhang} [J. Graph Theory 25, No. 3, 173-184 (1997; Zbl 0881.05066)] it was proved that \(\alpha \leq \delta + 2\), and moreover, \(G\) is Hamiltonian if \(\alpha \leq \delta + 1\). In the present paper it is shown that \(G\) is Hamiltonian if \(\alpha = \delta + 2\), and thus the conjecture is proved. A class of 3-\(\gamma\)-critical graphs with \(\alpha = \delta + 2\) is provided as well.
0 references
domination-critical graphs
0 references
Hamiltonicity
0 references
longest cycles
0 references