Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\)
type: Item
instance of: scholarly article
title: Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\)
zbMATH Open document ID: 0916.05038
DOI: 10.1016/S0166-218X(98)00149-8
author: Feng Tian
author: Bing Wei
author: Lei Zhang
published in: Discrete Applied Mathematics
publication date: 1999-07-07T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1274839
zbMATH Keywords: domination-critical graphs
zbMATH Keywords: Hamiltonicity
zbMATH Keywords: longest cycles
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
cites work: Q4879160
cites work: Independence and hamiltonicity in 3-domination-critical graphs
cites work: Some properties of 3-domination-critical graphs
cites work: Q4693374
cites work: Critical concepts in domination
cites work: Domination critical graphs
cites work: Hamiltonian properties of domination-critical graphs
cites work: Q4030536
full work available at URL: s0166-218x(98)00149-8
OpenAlex ID: W2093743709
Recommended article: Hamilton-connectivity of 3-domination critical graphs with \(\alpha = \delta + 2\)
Recommended article: Hamilton-connectivity of 3-domination-critical graphs with \(\alpha \leqslant\delta\)
Recommended article: Hamilton-connectivity of 3-domination critical graphs with \(\alpha =\delta +1\geqslant 5\)
Recommended article: On hamiltonicity of \(P_{3}\)-dominated graphs
Recommended article: Independence and hamiltonicity in 3-domination-critical graphs
Recommended article: Hamiltonian properties of the \(3\)-\((\gamma ,2)\)-critical graphs.
Recommended article: Q3017045
Recommended article: Q3572623
Recommended article: Hamiltonicity of \(3_t\)EC graphs with \(\alpha=\kappa +1\)
Recommended article: Hamiltonian properties of domination-critical graphs
description: scientific article; zbMATH DE number 1274839