Cycles within specified distance from each vertex. (Q1427481): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2003.05.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2016731369 / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
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