Two sufficient conditions for graphs to admit path factors

Abstract

Let $\mathcal{A}$ be a set of connected graphs. Then a spanning subgraph $A$ of $G$ is called an $\mathcal{A}$-factor if each component of $A$ is isomorphic to some member of $\mathcal{A}$. Especially, when every graph in $\mathcal{A}$ is a path, $A$ is a path factor. For a positive integer $d\ge 2$, we write ${\mathcal{P}}_{\ge d}=\{P_i|i\ge d\}$. Then a ${\mathcal{P}}_{\ge d}$-factor means a path factor in which every component admits at least $d$ vertices. A graph $G$ is called a $({\mathcal{P}}_{\ge d},m)$-factor deleted graph if $G-E^{\prime }$ admits a ${\mathcal{P}}_{\ge d}$-factor for any $E^{\prime }\subseteq E(G)$ with $|E^{\prime }|=m$. A graph $G$ is called a $({\mathcal{P}}_{\ge d},k)$-factor critical graph if $G-Q$ has a ${\mathcal{P}}_{\ge d}$-factor for any $Q\subseteq V(G)$ with $|Q|=k$. In this paper, we present two degree conditions for graphs to be $({\mathcal{P}}_{\ge 3},m)$-factor deleted graphs and $({\mathcal{P}}_{\ge 3},k)$-factor critical graphs. Furthermore, we show that the two results are best possible in some sense.

11 pages