1 Introduction
All graphs in this paper are finite simple graphs. Let G be a graph. The vertex set of G is denoted by
$V(G)$
and the edge set of G is denoted by
$E(G)$
. We write
$d_G(x)$
for the degree of a vertex x in G. Let X be a vertex subset of G. We write
$G[X]$
for the subgraph of G induced by X and
$G-X$
for
$G[V(G){\setminus } X]$
. A vertex subset X of G is called independent if
$G[X]$
has no edges. We denote by
$i(G)$
the number of isolated vertices of G, by
$\omega (G)$
the number of components of G and by
$\kappa (G)$
the vertex connectivity of G. The complete graph of order n is denoted by
$K_n$
and the path of order n is denoted by
$P_n$
. For two graphs
$G_1$
and
$G_2$
, we use
$G_1\cup G_2$
to denote the union of
$G_1$
and
$G_2$
and
$G_1\vee G_2$
to denote the join of
$G_1$
and
$G_2$
.
A spanning subgraph whose components are paths is called a path factor. We write
$P_{\geq n}=\{P_i \mid i\geq n\}$
. Then a
$P_{\geq n}$
-factor means a path factor in which each component possesses at least n vertices. Johnson et al. [Reference Johnson, Paulusma and Wood7] derived a sufficient condition for a graph to admit a path factor. Zhou [Reference Zhou16] studied the existence of
$P_{\geq 3}$
-factors in graphs. Zhou et al. [Reference Zhou, Bian and Pan17] showed some sufficient conditions for graphs having
$P_{\geq 3}$
-factors. Kaneko [Reference Kaneko8] obtained a characterisation for
$P_{\geq 3}$
-factors of graphs and Kano et al. [Reference Kano, Katona and Király9] gave a shorter proof of Kaneko’s result. Kelmans [Reference Kelmans11] discussed the existence of path factors in vertex deleted graphs. Zhou et al. [Reference Zhou, Xu and Xu22] discussed some problems on component factors of graphs.
A graph G is called a
$P_{\geq n}$
-factor covered graph if G possesses a
$P_{\geq n}$
-factor including e for every
$e\in E(G)$
. Zhou [Reference Zhou15] derived two results on
$P_{\geq 2}$
-factor and
$P_{\geq 3}$
-factor covered graphs. Zhou et al. [Reference Zhou, Wu and Zhang21] presented three sufficient conditions for the existence of
$P_{\geq 3}$
-factor covered graphs. Zhang and Zhou [Reference Zhang and Zhou14] found two criteria for
$P_{\geq 2}$
-factor and
$P_{\geq 3}$
-factor covered graphs.
A spanning subgraph F of a graph G is called a 1-factor of G if
$d_F(x)=1$
for any
$x\in V(G)$
. A graph R is factor critical if
$R-\{x\}$
contains a 1-factor for every
$x\in V(R)$
. Assume that R is a factor-critical graph with vertex set
$V(R)=\{x_1,x_2,\ldots ,x_n\}$
. By adding new vertices
$y_1,y_2,\ldots ,y_n$
together with new edges
$x_1y_1,x_2y_2,\ldots ,x_ny_n$
to R, a new graph called a sun is formed. According to Kaneko,
$K_1$
and
$K_2$
are also suns. A sun with at least six vertices is called a big sun. A component of a graph G is said to be a sun component if it is isomorphic to a sun. We denote by
$sun(G)$
the number of sun components of G.
Zhang and Zhou [Reference Zhang and Zhou14] gave a necessary and sufficient condition for the existence of
$P_{\geq 3}$
-factor covered graphs by using
$sun(G)$
.
Theorem 1.1 [Reference Zhang and Zhou14].
A connected graph G is a
$P_{\geq 3}$
-factor covered graph if and only if
$sun(G-X)\leq 2|X|-\varepsilon (X)$
for any subset X of
$V(G)$
, where
$\varepsilon (X)$
is defined by
$$ \begin{align*} \varepsilon(X)= \begin{cases} 2&\quad\mbox{if } X \mbox{ is not an independent set},\\ 1&\quad\mbox{if } X \mbox{ is a nonempty independent set and } G-X \mbox{ has a nonsun}\\ &\quad\mbox{component},\\ 0&\quad\mbox{otherwise}.\\ \end{cases} \end{align*} $$
A graph G is called a
$(P_{\geq n},k)$
-factor-critical covered graph if for any
$D\subseteq V(G)$
with
$|D|=k$
,
$G-D$
is a
$P_{\geq n}$
-factor covered graph. We establish two results on the existence of
$(P_{\geq 3},k)$
-factor-critical covered graphs, which we prove in Sections 2 and 3.
2 Toughness and
$(P_{\geq 3},k)$
-factor-critical covered graphs
The toughness
$t(G)$
of a graph G was first defined by Chvátal in [Reference Chvátal1] as follows. If G is complete,
$t(G)=+\infty $
. If G is not complete,
$$ \begin{align*}t(G)=\min\bigg\{\frac{|X|}{\omega(G-X)}: X\subseteq V(G), \omega(G-X)\geq2\bigg\}. \end{align*} $$
The relationships between toughness and graph factors were studied by Enomoto et al. [Reference Enomoto, Jackson, Katerinis and Satio2], Katerinis [Reference Katerinis10], Liu and Zhang [Reference Liu and Zhang12], Zhou et al. [Reference Zhou, Sun and Liu20], Gao et al. [Reference Gao, Guirao and Chen3] and Gao et al. [Reference Gao, Wang and Dimitrov6]. Zhou et al. [Reference Zhou, Wu and Zhang21] gave a toughness condition for the existence of
$P_{\geq 3}$
-factor covered graphs.
Theorem 2.1 [Reference Zhou, Wu and Zhang21].
A connected graph G with
$|V(G)|\geq 3$
is
$P_{\geq 3}$
-factor covered if its toughness
$t(G)>\tfrac 23$
.
We extend Theorem 2.1 to a toughness condition for a graph to be
$(P_{\geq 3},k)$
-factor- critical covered.
Theorem 2.2. Let
$k\geq 0$
be an integer and let G be a graph with
$|V(G)|\geq k+3$
and
$\kappa (G)\geq k+1$
. If
$t(G)>{(2+k)}/{3}$
, then G is a
$(P_{\geq 3},k)$
-factor-critical covered graph.
Proof. Theorem 2.2 obviously holds for a complete graph G with
$|V(G)|\geq k+3$
. Hence, we assume that G is a noncomplete graph. For any
$Q\subseteq V(G)$
with
$|Q|=k$
, let
$H=G-Q$
. Since
$\kappa (G)\geq k+1$
, we easily see that H is connected. To prove Theorem 2.2, we only need to verify that H is a
$P_{\geq 3}$
-factor covered graph. To the contrary, we assume that H is not a
$P_{\geq 3}$
-factor covered graph. Then, by Theorem 1.1, there exists some subset X of
$V(H)$
satisfying
$$ \begin{align} sun(H-X)\geq2|X|-\varepsilon(X)+1. \end{align} $$
Claim:
$X\neq \emptyset $
.
Indeed, assume that
$X=\emptyset $
. Then
$\varepsilon (X)=0$
and it follows from (2.1) that
$sun(H)\geq 1$
. Note that H is connected and so
$sun(H)\leq \omega (H)=1$
. Thus,
$$ \begin{align} sun(H)=\omega(H)=1. \end{align} $$
Since
$|V(G)|\geq k+3$
and
$H=G-Q$
, it follows that
$|V(H)|\geq 3$
. Combining this with (2.2), H is a big sun (for, otherwise,
$H=K_1$
or
$K_2$
and then
$|V(H)|\leq 2$
, so
$|V(G)|= |V(H)|+|Q|\leq k+2$
, contradicting
$|V(G)|\geq k+3$
). Let R be the factor-critical subgraph of H. Since H is a big sun, it follows that
$|V(H)|\geq 6$
and so
$|V(R)|=|V(H)\setminus V(R)|\geq 3$
. For any two distinct vertices
$u_1,u_2\in V(H)\setminus V(R)$
, we have
$d_H(u_1)=d_H(u_2)=1$
and there exist two different vertices
$v_1,v_2\in V(R)$
such that
$u_1v_1\in E(H)$
and
$u_2v_2\in E(H)$
. Thus, we easily see that
$$ \begin{align*} \omega(G-(Q\cup\{v_1,v_2\}))=\omega(H-\{v_1,v_2\})\geq3 \end{align*} $$
and so
$$ \begin{align*} t(G)\leq\frac{|Q\cup\{v_1,v_2\}|}{\omega(G-(Q\cup\{v_1,v_2\}))}=\frac{2+k}{\omega(G-(Q\cup\{v_1,v_2\}))}\leq\frac{2+k}{3}, \end{align*} $$
contradicting
$t(G)>{(2+k)}/{3}$
. The claim is verified.
According to the claim,
$|X|\geq 1$
. Next, we discuss two cases.
Case 1.
$|X|=1$
.
Subcase 1.1.
$H-X$
contains a nonsun component.
Evidently,
$\varepsilon (X)=1$
by the definition of
$\varepsilon (X)$
. Then, from (2.1) and
$\varepsilon (X)=1$
,
$$ \begin{align} sun(H-X)\geq2|X|-\varepsilon(X)+1=2|X|=2. \end{align} $$
Note that
$H-X$
contains a nonsun component. Together with (2.3), this gives
$$ \begin{align*}\omega(H-X)\geq sun(H-X)+1\geq3. \end{align*} $$
Combining this with
$H=G-Q$
and the definition of
$t(G)$
,
$$ \begin{align*}t(G)\leq\frac{|Q\cup X|}{\omega(G-(Q\cup X))}=\frac{|Q|+|X|}{\omega(H-X)}\leq\frac{1+k}{3}, \end{align*} $$
contradicting
$t(G)>{(2+k)}/{3}$
.
Subcase 1.2.
$H-X$
does not contain a nonsun component.
Apparently,
$\varepsilon (X)=0$
by the definition of
$\varepsilon (X)$
. Using (2.1),
$$ \begin{align*}sun(H-X)\geq2|X|-\varepsilon(X)+1=2|X|+1=3. \end{align*} $$
From
$t(G)>{(2+k)}/{3}$
,
$H=G-Q$
,
$\omega (H-X)\geq sun(H-X)\geq 3$
and the definition of
$t(G)$
,
$$ \begin{align*}\frac{2+k}{3}<t(G)\leq\frac{|Q\cup X|}{\omega(G-(Q\cup X))}=\frac{|Q|+|X|}{\omega(H-X)}\leq\frac{1+k}{3}, \end{align*} $$
which is a contradiction.
Case 2.
$|X|\geq 2$
.
From its definition,
$\varepsilon (X)\leq 2$
. Using this fact and (2.1),
$$ \begin{align} sun(H-X)\geq2|X|-\varepsilon(X)+1\geq2|X|-1\geq3. \end{align} $$
From (2.4),
$|X|\geq 2$
,
$H=G-Q$
,
$\omega (H-X)\geq sun(H-X)$
,
$t(G)>{(2+k)}/{3}$
and the definition of
$t(G)$
,
$$ \begin{align*} \frac{2+k}{3}<t(G) & \leq\frac{|Q\cup X|}{\omega(G-(Q\cup X))} =\frac{|Q|+|X|}{\omega(H-X)}\leq\frac{k+|X|}{sun(H-X)}\\ &\leq\frac{k+|X|}{2|X|-1}=\frac{1}{2}+\frac{2k+1}{2(2|X|-1)}\leq\frac{1}{2}+\frac{2k+1}{6}\\ &=\frac{2+k}{3}, \end{align*} $$
which is a contradiction. This finishes the proof of Theorem 2.2.
Remark 2.3. We give an example to illustrate that the toughness condition in Theorem 2.2 is sharp, that is, the toughness condition
$t(G)>{(2+k)}/{3}$
in Theorem 2.2 cannot be changed to
$t(G)\geq {(2+k)}/{3}$
.
Let
$k\geq 0$
be an integer and
$G=K_{k+2}\vee (H_1\cup H_2\cup H_3)$
, where
$H_1,H_2$
and
$H_3$
are three suns. For any
$Q\subseteq V(K_{k+2})$
with
$|Q|=k$
, let
$H=G-Q=K_2\vee (H_1\cup H_2\cup H_3)$
. Select
$X=V(K_2)\subseteq V(H)$
. Thus,
$\kappa (G)=k+2>k+1$
,
$sun(H-X)=\omega (H-X)=3$
and
$$ \begin{align*}t(G)=\frac{|Q\cup X|}{\omega(G-(Q\cup X))}=\frac{|Q|+|X|}{\omega(H-X)}=\frac{2+k}{3}.\end{align*} $$
Since X is not an independent set, we derive
$\varepsilon (X)=2$
. Therefore,
$$ \begin{align*}sun(H-X)=3>2=2|X|-\varepsilon(X). \end{align*} $$
According to Theorem 1.1, H is not
$P_{\geq 3}$
-factor covered and so G is not
$(P_{\geq 3},k)$
-factor- critical covered.
3 Isolated toughness and
$(P_{\geq 3},k)$
-factor-critical covered graphs
Yang et al. [Reference Yang, Ma and Liu13] introduced the isolated toughness
$I(G)$
of a graph G. If G is complete,
$I(G)=\infty $
. If G is not complete,
$$ \begin{align*}I(G)=\min\bigg\{\frac{|X|}{i(G-X)}:X\subseteq V(G), i(G-X)\geq2\bigg\}. \end{align*} $$
The relationships between isolated toughness and graph factors were discussed by Yang et al. [Reference Yang, Ma and Liu13], Zhou et al. [Reference Zhou, Pan and Xu18], Zhou et al. [Reference Zhou, Sun and Liu19], Gao et al. [Reference Gao, Liang and Chen4] and Gao and Wang [Reference Gao and Wang5]. Zhou et al. [Reference Zhou, Wu and Zhang21] gave an isolated toughness condition for the existence of
$P_{\geq 3}$
-factor covered graphs.
Theorem 3.1 [Reference Zhou, Wu and Zhang21].
A connected graph G with
$|V(G)|\geq 3$
is
$P_{\geq 3}$
-factor covered if its isolated toughness
$I(G)>\tfrac 53$
.
We generalise Theorem 3.1 and give an isolated toughness condition for a graph to be
$(P_{\geq 3},k)$
-factor-critical covered.
Theorem 3.2. Let
$k\geq 0$
be an integer and let G be a graph with
$\kappa (G)\geq k+2$
. If
$I(G)>{(5+k)}/{3}$
, then G is a
$(P_{\geq 3},k)$
-factor-critical covered graph.
Proof. Note that
$|V(G)|\geq k+3$
since
$\kappa (G)\geq k+2$
. If G is a complete graph, then it is obvious that G is a
$(P_{\geq 3},k)$
-factor-critical covered graph because
$|V(G)|\geq k+3$
. From now on, we assume that G is a noncomplete graph.
For any
$Q\subseteq V(G)$
with
$|Q|=k$
, let
$H=G-Q$
. Since
$\kappa (G)\geq k+2$
, we easily see that H is connected. To prove Theorem 3.2, we only need to show that H is a
$P_{\geq 3}$
-factor covered graph. To the contrary, suppose that H is not a
$P_{\geq 3}$
-factor covered graph. Then it follows from Theorem 1.1 that there exists some subset X of
$V(H)$
such that
$$ \begin{align} sun(H-X)\geq2|X|-\varepsilon(X)+1. \end{align} $$
Assume that there exist a isolated vertices,
$b \ K_2$
’s and c big sun components
$H_1,H_2,\ldots ,H_c$
, where
$|V(H_i)|\geq 6$
for
$1\leq i\leq c$
, in
$H-X$
. Clearly,
$$ \begin{align} sun(H-X)=a+b+c. \end{align} $$
We select one vertex from each
$K_2$
component of
$H-X$
and denote the set of these vertices by M. Let
$R_i$
be the factor-critical subgraph of
$H_i$
for
$1\leq i\leq c$
. We write
$N_i=V(H_i)\setminus V(R_i)$
,
$i=1,2,\ldots ,c$
. It is obvious that
$|M|=b$
and
$i(H_i-V(R_i))=|N_i|=|V(R_i)|=\tfrac 12 |V(H_i)|$
. Thus,
$$ \begin{align} i(G-(Q\cup X\cup M\cup V(R_1)\cup\cdots\cup V(R_c)))=a+b+\sum_{i=1}^{c}|N_i|\geq a+b+3c. \end{align} $$
Next, we consider three cases.
Case 1.
$|X|=0$
.
In this case,
$\varepsilon (X)=0$
. From (3.1),
$$ \begin{align} sun(H)\geq1. \end{align} $$
From (3.4),
$sun(H)\leq \omega (H)$
and, since H is connected,
$ 1\leq sun(H)\leq \omega (H)=1, $
which implies that
$$ \begin{align} sun(H)=\omega(H)=1. \end{align} $$
Since
$|V(G)|\geq k+3$
and
$H=G-Q$
, we have
$|V(H)|\geq 3$
. Combining this with (3.5) shows that H is a big sun. (Otherwise,
$H=K_1$
or
$K_2$
, giving
$|V(H)|\leq 2$
and so
$|V(G)|=|V(H)|+|Q|\leq k+2$
, contradicting
$|V(G)|\geq k+3$
.) Let R be the factor-critical subgraph of H. Since H is a big sun, it follows that
$|V(H)|\geq 6$
and so
$|V(R)|=|V(H)\setminus V(R)|\geq 3$
. For three different vertices
$u_1,u_2,u_3\in V(H)\setminus V(R)$
, we easily see that
$d_H(u_1)=d_H(u_2)=d_H(u_3)=1$
and there exist three distinct vertices
$v_1,v_2,v_3\in V(R)$
with
$u_iv_i\in E(H)$
for
$1\leq i\leq 3$
. Hence,
$$ \begin{align*}i(G-(Q\cup\{v_1,v_2,v_3\}))=\omega(H-\{v_1,v_2,v_3\})\geq3 \end{align*} $$
and so
$$ \begin{align*}I(G)\leq\frac{|Q\cup\{v_1,v_2,v_3\}|}{\omega(G-(Q\cup\{v_1,v_2,v_3\}))}\leq\frac{3+k}{3}, \end{align*} $$
contradicting
$I(G)>{(5+k)}/{3}$
.
Case 2.
$|X|=1$
.
Evidently,
$\varepsilon (X)\leq 1$
. According to (3.1),
$$ \begin{align} sun(H-X)\geq2|X|-\varepsilon(X)+1\geq2|X|=2. \end{align} $$
On the other hand, since
$\kappa (G)\geq k+2$
,
$|Q|=k$
and
$H=G-Q$
, we easily see that
$H-X$
is connected and so
$\omega (H-X)=1$
. Combining this with
$sun(H-X)\leq \omega (H-X)$
,
$$ \begin{align*}sun(H-X)\leq1, \end{align*} $$
which contradicts (3.6).
Case 3.
$|X|\geq 2$
.
Note that
$\varepsilon (X)\leq 2$
. It follows from (3.1) and (3.2) that
$$ \begin{align} sun(H-X)=a+b+c\geq2|X|-\varepsilon(X)+1\geq2|X|-1\geq3. \end{align} $$
$$ \begin{align} i(G-(Q\cup X\cup M\cup V(R_1)\cup\cdots\cup V(R_c)))=a+b+\sum_{i=1}^{c}|N_i|\geq a+b+c\geq3. \end{align} $$
By (3.7),
$\sum _{i=1}^{c}|V(R_i)|=\sum _{i=1}^{c}|N_i|=\sum _{i=1}^{c}\tfrac 12|V(H_i)|\geq 3$
,
$I(G)>{(5+k)}/{3}$
and the definition of
$I(G)$
,
$$ \begin{align*} \frac{5+k}{3}<I(G) & \leq\frac{|Q\cup X\cup M\cup V(R_1)\cup\cdots\cup V(R_c)|}{i(G-(Q\cup X\cup M\cup V(R_1)\cup\cdots\cup V(R_c)))}\\[2pt] &=\frac{k+|X|+b+\sum_{i=1}^{c}|V(R_i)|}{a+b+\sum_{i=1}^{c}|N_i|} =\frac{k+|X|+b+\sum_{i=1}^{c}|N_i|}{a+b+\sum_{i=1}^{c}|N_i|}\\[2pt] &=1+\frac{k+|X|-a}{a+b+\sum_{i=1}^{c}|N_i|} \leq1+\frac{k+|X|}{a+b+c} \\[2pt] &\leq1+\frac{k+\frac{1}{2}(a+b+c+1)}{a+b+c} =\frac{3}{2}+\frac{2k+1}{2(a+b+c)}\\[2pt] &\leq\frac{3}{2}+\frac{2k+1}{6} =\frac{5+k}{3}, \end{align*} $$
which is a contradiction. This completes the proof of Theorem 3.2.
Remark 3.3. We give an example to illustrate that the isolated toughness condition in Theorem 3.2 is sharp, that is, the isolated toughness condition
$I(G)>{(5+k)}/{3}$
in Theorem 3.2 cannot be changed to
$I(G)\geq {(5+k)}/{3}$
.
Let k be a nonnegative integer and let
$G=K_{k+2}\vee (3K_2)$
. It is easily seen that
$\kappa (G)=k+2$
and
$I(G)={(5+k)}/{3}$
. For any
$Q\subseteq V(K_{k+2})$
with
$|Q|=k$
, we write
$H=G-Q=K_2\vee (3K_2)$
. Set
$X=V(K_{k+2}){\setminus } V(K_k)=V(K_2)\subseteq V(H)$
. Since X is not an independent set,
$\varepsilon (X)=2$
. Therefore,
$$ \begin{align*}sun(H-X)=3>2=2|X|-\varepsilon(X). \end{align*} $$
In light of Theorem 1.1, H is not
$P_{\geq 3}$
-factor covered and so G is not
$(P_{\geq 3},k)$
-factor- critical covered.
Acknowledgement
The authors are grateful to the anonymous referees for giving many helpful comments and suggestions in improving this paper.
