Cycles within specified distance from each vertex. (Q1427481): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A sufficient condition for dominating cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Existence of Δλ-cycles and Δλ-paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4350166 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on Hamiltonian circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Theorems on Abstract Graphs / rank | |||
Normal rank |
Latest revision as of 15:27, 6 June 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