Back to Search
Start Over
On the existence of vertex-disjoint subgraphs with high degree sum.
- Source :
-
Discrete Applied Mathematics . Feb2018, Vol. 236, p84-95. 12p. - Publication Year :
- 2018
-
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 s 1 , s 2 ≥ 2 are integers and G is a non-complete graph with σ 2 ( G ) ≥ 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 σ 2 ( H i ) ≥ 2 s i − 1 . (ii) If s 1 , s 2 ≥ 2 are integers and G is a triangle-free graph of order at least 3 with σ 2 ( G ) ≥ 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 2 s i with σ 2 ( H i ) ≥ 2 s i − 1 . By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*GRAPH theory
*GRAPHIC methods
*GRAPH connectivity
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 236
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 126943939
- Full Text :
- https://doi.org/10.1016/j.dam.2017.10.029