Journal of Graph Theory · 1997 · 11 citations · 0 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCircuit TheoryCombinatoricsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryEdge CoverGraph Theory AnalysisGraph Theory Models
We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e1, …, ek of G, there exist k vertex-disjoint cycles C1, …, Ck in G such that ei ∈ E(Ci) for all i ∈ {1, …, k} and V(C1 ∪ ···∪ Ck) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997