Article ID Journal Published Year Pages File Type
4648235 Discrete Mathematics 2008 4 Pages PDF
Abstract

For a set HH of connected graphs, a spanning subgraph HH of a graph GG is an HH-factor   if every component of HH is isomorphic to some member of HH. Amahashi and Kano [A. Amahashi, M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6] proved that a graph GG satisfying i(G−S)≤m|S|i(G−S)≤m|S| for every S⊂V(G)S⊂V(G) has a {K1,l:1≤l≤m}{K1,l:1≤l≤m}-factor, where i(G)i(G) is the number of isolated vertices in GG and K1,lK1,l denotes the star with ll edges. Here we exclude small stars from the set and prove that a graph GG satisfying i(G−S)≤1m|S| for every S⊂V(G)S⊂V(G) has a {K1,l:m≤l≤2m}{K1,l:m≤l≤2m}-factor.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,