Premium
Independence number, connectivity, and r‐factors
Author(s) -
Nishimura Tsuyoshi
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130109
Subject(s) - combinatorics , independence number , mathematics , graph , integer (computer science) , discrete mathematics , computer science , programming language
We show that if r ⩾ 1 is an odd integer and G is a graph with | V(G) | even such that k ( G ) ⩾ ( r + 1) 2 /2 and ( r + 1) 2 α( G ) ⩽ 4 rk ( G ), then G has an r ‐factor; if r ⩾ 2 is even and G is a graph with k ( G ) ⩾ r ( r + 2)/2 and ( r + 2)α( G ) ⩽ 4 k ( G ), then G has an r ‐factor (where k ( G ) and α( G ) denote the connectivity and the independence number of G , respectively).