On the existence of vertex-disjoint subgraphs with high degree sums

Shuya Chiba, Nicolas Lichiardopol

Published 2015-03-11Version 1

For a graph $G$, we denote by $\sigma_{2}(G)$ the minimum degree sum of two non-adjacent vertices if $G$ is non-complete; otherwise, $\sigma_{2}(G) = +\infty$. In this paper, we prove the following two results; (i) If $s_{1}$ and $s_{2}$ are integers with $s_{1}, s_{2} \ge 2$ and if $G$ is a non-complete graph with $\sigma_{2}(G) \ge 2(s_{1} + s_{2} + 1) - 1$, then $G$ contains two vertex-disjoint subgraphs $H_{1}$ and $H_{2}$ such that each $H_{i}$ is a graph of order at least $s_{i}+1$ with $\sigma_{2}(H_{i}) \ge 2s_{i} - 1$. (ii) If $s_{1}$ and $s_{2}$ are integers with $s_{1}, s_{2} \ge 2$ and if $G$ is a non-complete triangle-free graph with $\sigma_{2}(G) \ge 2(s_{1} + s_{2}) - 1$, then $G$ contains two vertex-disjoint subgraphs $H_{1}$ and $H_{2}$ such that each $H_{i}$ is a graph of order at least $2s_{i}$ with $\sigma_{2}(H_{i}) \ge 2s_{i} - 1$. By using this kind of results, we also give some corollaries concerning the degree conditions for vertex-disjoint cycles.