Research Article

Some results about component factors in graphs^⋆

School of Science, Jiangsu University of Science and Technology Mengxi Road 2, Zhenjiang, Jiangsu 212003, P.R. China

^* Corresponding author: zsz_cumt@163.com

Received: 14 July 2016
Accepted: 26 May 2017

Abstract

For a set ℋ of connected graphs, a spanning subgraph H of a graph G is called an ℋ-factor of G if every component of H is isomorphic to a member ofℋ. An H-factor is also referred as a component factor. If each component of H is a star (resp. path), H is called a star (resp. path) factor. By a P_≥ k-factor (k positive integer) we mean a path factor in which each component path has at least k vertices (i.e. it has length at least k − 1). A graph G is called a P_≥ k-factor covered graph, if for each edge e of G, there is a P_≥ k-factor covering e. In this paper, we prove that (1) a graph G has a {K_1,1,K_1,2, … ,K_1,k}-factor if and only if bind(G) ≥ 1/k, where k ≥ 2 is an integer; (2) a connected graph G is a P_≥ 2-factor covered graph if bind(G) > 2/3; (3) a connected graph G is a P_≥ 3-factor covered graph if bind(G) ≥ 3/2. Furthermore, it is shown that the results in this paper are best possible in some sense.