Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650000 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,sr,s be nonnegative integers and let GG be a graph with |V(G)|≥3r+4s|V(G)|≥3r+4s and minimal degree δ(G)≥2r+3sδ(G)≥2r+3s. Then GG contains a collection of r+sr+s vertex disjoint cycles, ss of them with a chord. We prove the conjecture for r=0,s=2r=0,s=2 and for s=1s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on nn vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arie Bialostocki, Daniel Finkel, András Gyárfás,