A note on dominating cycles in 2-connected graphs
type: Item
instance of: scholarly article
title: A note on dominating cycles in 2-connected graphs
zbMATH Open document ID: 0864.05052
DOI: 10.1016/0012-365X(94)00364-O
author: D. Bauer
author: E. Schmeichel
author: Henk Jan Veldman
published in: Discrete Mathematics
publication date: 1997-06-22T00:00:00Z
review text: The authors and \textit{A. Morgana} [Discrete Math. 79, No. 1, 59-70 (1990; Zbl 0713.05041)] proved that in a 1-tough graph \(G\) on \(n\) vertices, with \(d(u)+d(v)+d(w)\geq n\) for all triples of independent vertices, every longest cycle is dominating. As an improvement, in the present paper this is essentially extended to the more general class of 2-connected graphs, by showing the following. Let \(G\) be a 2-connected graph with \(n\) vertices, with \(d(u)+d(v)+d(w)\geq n\) for all triples of independent vertices. Then every longest cycle is dominating, unless \(G\) is a spanning subgraph of a graph belonging to one of four special classes. These are explicitly described in the article.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 932520
zbMATH Keywords: dominating cycles
zbMATH Keywords: Hamiltonian graph
zbMATH Keywords: longest cycle
zbMATH Keywords: 2-connected graphs
reviewed by: Raffaele Scapellato
MaRDI profile type: Publication
cites work: Toughness, minimum degree, and the existence of 2‐factors
cites work: Q3971997
cites work: Hamiltonian properties of graphs with large neighborhood unions
cites work: Recognizing tough graphs is NP-hard
cites work: Q3984510
cites work: Long cycles in graphs with large degree sums
cites work: Q4873795
cites work: Q4871126
cites work: Q4094891
cites work: Large cycles in graphs
cites work: Q4192100
cites work: Long cycles, degree sums and neighborhood unions
cites work: Q3818315
cites work: Tough graphs and Hamiltonian circuits.
cites work: On Maximal Circuits in Finite Graphs
cites work: A lower bound for the circumference of a graph
cites work: Q3724373
cites work: Q3822194
cites work: Existence of dominating cycles and paths
full work available at URL: 0012-365x(94)00364-o
OpenAlex ID: W2079553117
description: scientific article; zbMATH DE number 932520