Cyclability of id-cycles in graphs

الأصل · EN

Let G be a graph on n vertices and C'=v₀v₁ vₚ₋₁v₀ a vertex sequence of G with p≥ 3 (vᵢ≠ vⱼ for all i,j=0,1,,p-1, i≠ j). If for any successive vertices vᵢ, vᵢ₊₁ on C', either vᵢvᵢ₊₁∈ E(G) or both of the first implicit-degrees of vᵢ and vᵢ₊₁ are at least n/2 (indices are taken modulo p), then C' is called an id-cycle of G. In this paper, we prove that for every id-cycle C', there exists a cycle C in G with V(C') V(C). This generalizes several early results on the Hamiltonicity and cyclability of graphs.