Long dominating cycles in graphs
type: Item
instance of: scholarly article
title: Long dominating cycles in graphs
zbMATH Open document ID: 0887.05032
DOI: 10.1016/S0012-365X(97)00005-8
author: Ruqun Shen
author: Feng Tian
published in: Discrete Mathematics
publication date: 1998-04-28T00:00:00Z
review text: A cycle \(C\) in a graph \(G\) is a dominating cycle, or \(D\)-cycle, if \(V(G) - V(C)\) is an independent set in \(G\). Let \(\text{NC}2 = \text{ min} \{ |N(u) \cup N(v)|: \text{ dist} (u,v) = 2 \}\). This paper proves that if a graph on \(n\) vertices with minimum degree 2 contains a \(D\)-cycle, then it contains a \(D\)-cycle of length at least min\(\{ n, 2\text{NC}2-3 \}\). The authors suggest possible improvements to this and a related theorem.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1110123
zbMATH Keywords: dominating cycle
zbMATH Keywords: longest cycle
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Hamiltonian properties of graphs with large neighborhood unions
cites work: Q4192100
cites work: Q5422499
cites work: Long dominating cycles and paths in graphs with large neighborhood unions
cites work: Neighborhood unions and hamiltonicity of graphs
cites work: Q4849520
cites work: The circumference of a class of \(3\)-connected graphs
Recommended article: Q5453928
Recommended article: Long dominating cycles in graphs
Recommended article: Q4849520
Recommended article: On the length of longest dominating cycles in graphs
Recommended article: Long cycles in certain graphs of large degree
Recommended article: Q3744188
Recommended article: Long cycles in critical graphs
Recommended article: Long cycles in graphs with large degree sums
Recommended article: Long dominating cycles and paths in graphs with large neighborhood unions
Recommended article: Q3480078
description: scientific article; zbMATH DE number 1110123