Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650466 | Discrete Mathematics | 2008 | 4 Pages |
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
Daniel Finkel,