A sufficient condition for dominating cycles
type: Item
instance of: scholarly article
title: A sufficient condition for dominating cycles
zbMATH Open document ID: 0634.05045
DOI: 10.1016/0012-365X(87)90029-X
author: J. A. Bondy
author: Genghua Fan
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A cycle C of G is called a dominating cycle if every vertex of G is adjacent to at least one vector of C. Let \(R_ m(v)=\{u\in V(G):\) \(d(u,v)\leq m\}\). A cycle is called an m-dominating cycle if \(R_ m(v)\cap V(C)\geq n-2k\). \textit{B. N. Clark, C. J. Colbourn} and \textit{P. Erdős} [A conjecture on dominating cycles, Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf. Boca Raton/Fla. 1985, Congr. Numerantium 47, 189-197 (1985; Zbl 0622.05042)] conjectured: for a k- connected graph, \(k\geq 2\), on n vertices, if every \(k+1\) independent vertices \(x_ i\) (0\(\leq i\leq k)\) with \(R_ m(x_ i)\cap R_ m(x_ j)=\phi\) (0\(\leq i\neq j\leq k)\) satisfy the inequality \(\sum^{k}_{i=0}| R_ m(x_ i)| \geq n-2k\), then G has an m- dominating cycle. In this article the authors prove the conjecture in the case \(m=1\) and give an example showing that n-2k cannot be replace with n-2k-1. They also point out that \textit{P. Fraisse} \([D_{\lambda}\)-cycles and their applications for Hamiltonian graphs, preprint] has independently proved the conjecture in this case.
reviewed by: R. L. Hemminger
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4031736
zbMATH Keywords: dominating cycle
MaRDI profile type: Publication
cites work: Q3758869
Recommended article: Q3758869
Recommended article: Q3147265
Recommended article: A note on distance-dominating cycles
Recommended article: Q4388617
Recommended article: Q3011709
Recommended article: Q4004559
Recommended article: Q4858942
Recommended article: On a conjecture of Bondy
Recommended article: Circumference of a graph and its distance dominating longest cycles
Recommended article: Cycles within specified distance from each vertex.
description: scientific article; zbMATH DE number 4031736