Cycles within specified distance from each vertex. (Q1427481): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q1811077 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
Normal rank |
Revision as of 22:12, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles within specified distance from each vertex. |
scientific article |
Statements
Cycles within specified distance from each vertex. (English)
0 references
14 March 2004
0 references
Let \(f\) be a nonnegative integer-valued function defined on the vertex set of a graph \(G\). A cycle \(C\) in \(G\) is an \(f\)-dominating cycle if for each vertex \(x\) of \(G\), \(d_G(x,C) \leq f(x)\), where \(d\) is the distance function. A set \(S\) of vertices is \(f\)-stable if \(d_G(u,v) \geq f(u)+f(v)\) for any distinct vertices \(u\) and \(v\) of \(S\). Now let \(G\) be a \(k\)-connected graph (\(k \geq 2\)). If the largest \(f+1\)-stable set is no larger than \(k\), the authors show that \(G\) has an \(f\)-dominating cycle. Here \((f+1)(v)=f(v)+1\). This theorem generalizes results by Chvátal-Erdős on dominating cycles and results by Dirac on cycles through specified vertices.
0 references
dominating cycle
0 references
stable set
0 references
Hamiltonian cycle
0 references