Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871520 | Discrete Applied Mathematics | 2018 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shuya Chiba, Nicolas Lichiardopol,