2015/03/11 by Chiba, Shuya, Lichiardopol, Nicolas
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1503.03272
For a graph G, we denote by σ2(G) the minimum degree sum of two non-adjacent vertices if G is non-complete; otherwise, σ2(G) = +∞. In this paper, we prove the following two results: (i) If s1, s2 ≥ 2 are integers and G is a non-complete graph with σ2(G) ≥ 2(s1 + s2 + 1) - 1, then G contains two vertex-disjoint subgraphs H1 and H2 such that each Hi is a graph of order at least si+1 with σ2(Hi) ≥ 2si - 1. (ii) If s1, s2 ≥ 2 are integers and G is a triangle-free graph of order at least 3 with σ2(G) ≥ 2(s1 + s2) - 1, then G contains two vertex-disjoint subgraphs H1 and H2 such that each Hi is a graph of order at least 2si with σ2(Hi) ≥ 2si - 1. By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles.