Article ID Journal Published Year Pages File Type
4650466 Discrete Mathematics 2008 4 Pages PDF
Abstract

Hajnal and Corrádi proved that any simple graph on at least 3k3k vertices with minimal degree at least 2k2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G   be a simple graph with |V(G)|⩾4k|V(G)|⩾4k and minimal degree δ(G)⩾3kδ(G)⩾3k. Then G contains k independent chorded cycles. This result is sharp.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,