Premium
Regular factors in K 1, n free graphs
Author(s) -
Egawa Yoshimi,
Ota Katsuhiro
Publication year - 1991
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.3190150310
Subject(s) - combinatorics , mathematics , graph , induced subgraph , degree (music) , discrete mathematics , vertex (graph theory) , physics , acoustics
A graph is said to be K 1, n ‐free, if it contains no K 1, n as an induced subgraph. We prove that for n ⩾ 3 and r ⩾ n −1, if G is a K 1, n ‐free graph with minimum degree at least ( n 2 /4( n −1)) r + (3 n −6)/2 + ( n −1)/4 r , then G has an r ‐factor (in the case where r is even, the condition r ⩾ n −1 can be dropped).