|
|||||
|
|
Disjoint chorded cycles in graphs |
|
| Authors: | Arie Bialostocki |
| Affiliation: | a Department of Mathematics, University of Idaho, Moscow, ID 83844-1103, USA b Mathematics Department, University of Washington, Seattle, WA 98195, USA c Computer and Automation Research Institute, Hungarian Academy of Sciences, P.O. Box 63, Budapest, H-1518 Hungary |
| Abstract: | We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,s be nonnegative integers and let G be a graph with |V(G)|≥3r+4s and minimal degree δ(G)≥2r+3s. Then G contains a collection of r+s vertex disjoint cycles, s of them with a chord. We prove the conjecture for r=0,s=2 and for s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on n vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled. |
| Keywords: | Cycles Cycles with chords |
| 本文献已被 ScienceDirect 等数据库收录！ | |