Article ID Journal Published Year Pages File Type
4650000 Discrete Mathematics 2008 5 Pages PDF
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
, , ,