Some properties of 3-domination-critical graphs
type: Item
instance of: scholarly article
title: Some properties of 3-domination-critical graphs
zbMATH Open document ID: 0947.05059
DOI: 10.1016/S0012-365X(99)00038-2
author: Evelyne Flandrin
author: Feng Tian
author: Bing Wei
author: Lei Zhang
published in: Discrete Mathematics
publication date: 2000-11-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1334678
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: toughness
zbMATH Keywords: domination number
zbMATH Keywords: dominating cycle
reviewed by: Gerd Wegner
MaRDI profile type: Publication
cites work: Q3097395
cites work: Independence and hamiltonicity in 3-domination-critical graphs
cites work: Critical concepts in domination
cites work: Domination critical graphs
cites work: Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\)
cites work: Hamiltonian properties of domination-critical graphs
cites work: Q4030536
Wikidata QID: Q126988698
full work available at URL: s0012-365x(99)00038-2
OpenAlex ID: W2095295529
description: scientific article; zbMATH DE number 1334678