Premium
A degree condition for the existence of regular factors in K 1, n ‐free graphs
Author(s) -
Ota Katsuhiro,
Tokuda Taro
Publication year - 1996
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/(sici)1097-0118(199605)22:1<59::aid-jgt8>3.0.co;2-k
Subject(s) - combinatorics , mathematics , graph , degree (music) , induced subgraph , physics , vertex (graph theory) , acoustics
A graph is called K 1, n ‐free if it contains no K 1, n as an induced subgraph. Let n (≥3), r be integers (if r is odd, r ≥ n − 1). We prove that every K 1, n ‐free connected graph G with r | V (G)| even has an r ‐factor if its minimum degree is at least. \documentclass{article}\pagestyle{empty}\begin{document}$ \left(n+{{n-1}\over{r}}\right) \left\lceil {n\over{2(n-1)}}r \right\rceil - {{n-1}\over{r}}\left(\left\lceil {n\over{2(n-1)}}r \right\rceil \right)^2+n-3. $\end{document} This degree condition is sharp. © 1996 John Wiley & Sons, Inc.