Sufficient conditions for the existence of path-factors with given properties

Abstract

A spanning subgraph H of a graph G is called a [Formula: see text]-factor of G if every component of H is isomorphic to a path of order at least k, where [Formula: see text] is an integer. A graph G is called a [Formula: see text]-factor-critical graph if [Formula: see text] contains a [Formula: see text]-factor for any [Formula: see text] with [Formula: see text]. A graph G is called a [Formula: see text]-factor-deleted graph if [Formula: see text] has a [Formula: see text]-factor for any [Formula: see text] with [Formula: see text]. Intuitively, if a graph is dense enough, it will have a [Formula: see text]-factor. In this paper, we give some sufficient conditions for a graph to be a [Formula: see text]-factor-critical graph or a [Formula: see text]-factor-deleted graph. In this paper, we demonstrate that (i) G is a [Formula: see text]-factor-critical graph if its sun toughness [Formula: see text] and [Formula: see text]. (ii) G is a [Formula: see text]-factor-critical graph if its degree sum [Formula: see text] and [Formula: see text]. (iii) G is a [Formula: see text]-factor-deleted graph if its sun toughness [Formula: see text] and [Formula: see text]. (iv) G is a [Formula: see text]-factor-deleted graph if its degree sum [Formula: see text] and [Formula: see text].

Keywords

• path-factor
• sun toughness
• degree sum
• -factor-critical graph
• -factor-deleted graph
• 05C38