Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651229 | Discrete Mathematics | 2006 | 5 Pages |
Abstract
A graph G is called K1,nK1,n-free if G has no induced subgraph isomorphic to K1,nK1,n. Let n, a, b be integers with n⩾3n⩾3, a⩾1a⩾1, and a⩽b⩽a(n-2)+1a⩽b⩽a(n-2)+1. We prove that every connected K1,nK1,n-free graph G has a connected [a,b+n-⌈b/a⌉][a,b+n-⌈b/a⌉]-factor if G contains an [a,b][a,b]-factor. This result is sharp in the sense that there exists a connected K1,nK1,n-free graph which has an [a,b][a,b]-factor but no connected [a,b+n-⌈b/a⌉-1][a,b+n-⌈b/a⌉-1]-factor for b⩽a(n-2)+1b⩽a(n-2)+1.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Taro Tokuda,