On path-factor critical deleted (or covered) graphs

Abstract

Let $k\ge 2$ be an integer. A $P_{\ge k}$-factor of a graph G is its spanning subgraph each of whose components is a path of order at least k. A graph G is $P_{\ge k}$-factor covered if for any edge e of G, G has a $P_{\ge k}$-factor containing e. A graph G is $P_{\ge k}$-factor deleted if for any edge e of G, G has a $P_{\ge k}$-factor excluding e. A graph G is $(P_{\ge k},n)$-factor critical covered if for any $Q\subseteq V(G)$ with $|Q|=n$, the graph $G-Q$ is $P_{\ge k}$-factor covered. A graph G is $(P_{\ge k},n)$-factor critical deleted if for any $Q\subseteq V(G)$ with $|Q|=n$, the graph $G-Q$ is $P_{\ge k}$-factor deleted. Zhou et al. (Contribut Dis Math 14(1): 167–174, 2019) introduced the sun toughness of a graph G, which is denoted by s(G) and defined by

$$\begin{aligned} s(G)=\min \left\{ \frac{|X|}{sun(G-X)}:X\subseteq V(G),sun(G-X)\ge 2\right\} \end{aligned}$$

if G is not a complete graph; otherwise, $s(G)=+\infty$. In this article, we prove that (i) an $(n+r+2)$-connected graph G is $(P_{\ge 3},n)$-factor critical deleted if $s(G)>\frac{n+r+3}{2(r+2)}$, where $n\ge 0$ and $r\ge 0$ are two integers; (ii) an $(n+r+1)$-connected graph G is $(P_{\ge 3},n)$-factor critical covered if $s(G)>\frac{n+r+1}{2r+1}$, where $n\ge 0$ and $r\ge 1$ are two integers.

1 Introduction

We consider only undirected finite graphs without loops or multiple edges, unless explicitly stated otherwise. Let G be a graph, and let V(G) and E(G) denote the sets of vertices and edges of G, respectively. The degree of a vertex x in G, denoted by $d_G(x)$, is the number of vertices adjacent to x in G. We use i(G) and $\omega (G)$ to denote the number of isolated vertices and connected components of G, respectively. Let X be a vertex set of G and $E'$ be an edge set of G. Then $G-X$ denotes the resulting graph after removing the vertices of X from G, and $G-E'$ denotes the subgraph derived from G by removing $E'$. For notational simplicity, we write $G-x=G-\{x\}$ for $x\in V(G)$ and $G-e=G-\{e\}$ for $e\in E(G)$. A vertex set X of G is independent if no two elements in X are adjacent. Let $G_1$ and $G_2$ be two graphs. We denote by $G_1\cup G_2$ and $G_1\vee G_2$ the union and the join of $G_1$ and $G_2$, respectively. Let $P_n$, $C_n$ and $K_n$ denote the path, the cycle and the complete graph with n vertices, respectively.

A path-factor is a spanning subgraph F of G such that every component of F is a path. Let $k\ge 2$ be an integer. A $P_{\ge k}$-factor of a graph G is its spanning subgraph each of whose components is a path of order at least k. A graph G is $P_{\ge k}$-factor covered if for any edge e of G, G has a $P_{\ge k}$-factor containing e. A graph G is $P_{\ge k}$-factor deleted if for any edge e of G, G has a $P_{\ge k}$-factor excluding e. A graph G is said to be $(P_{\ge k},n)$-factor critical covered if for any $Q\subseteq V(G)$ with $|Q|=n$, the graph $G-Q$ is $P_{\ge k}$-factor covered. A graph G is said to be $(P_{\ge k},n)$-factor critical deleted if for any $Q\subseteq V(G)$ with $|Q|=n$, the graph $G-Q$ is $P_{\ge k}$-factor deleted.

Bazgan, Benhamdine, Li and Woźniak [1] verified that a 1-tough graph G of order at least 3 admits a $P_{\ge 3}$-factor. Kano, Lu and Yu [5] justified that a graph G contains a $P_{\ge 3}$-factor if $i(G-X)\le \frac{2}{3}|X|$ for all $X\subseteq V(G)$. Wang [7] claimed that a bipartite graph G admits a $P_{\ge 3}$-factor if and only if $i(G-X-M)\le 2|X|+|M|$ for any $X\subseteq V(G)$ and independent $M\subseteq E(G)$. Kelmans [6] showed some sufficient conditions for graphs to have path-factors. Zhou [10], Zhou, Bian and Sun [13] derived some sufficient conditions for graphs to be $P_{\ge 3}$-factor covered graphs. Gao, Wang and Chen [2] got some results on the existence of $P_{\ge 3}$-factor deleted graphs. Zhou [9], Zhou, Sun and Liu [15] obtained some results on the $P_{\ge 3}$-factor with given properties. Zhou [11], Zhou, Bian and Pan [12] presented some sufficient conditions for graphs to be $(P_{\ge 3},n)$-factor critical deleted graphs.

To characterize graphs admitting $P_{\ge 3}$-factors, Kaneko [3] introduced the concept of a sun. If $R-x$ admits a perfect matching for any $x\in V(R)$, then R is called a factor-critical graph. Let R be a factor-critical graph with vertex set $V(R)=\{x_1,x_2,\cdots ,x_n\}$. By adding new vertices $y_1,y_2,\cdots ,y_n$ together with new edges $x_1y_1,x_2y_2,\cdots ,x_ny_n$ to R, we derive a new graph H, which is called a sun. By Kaneko, $K_1$ and $K_2$ are also suns. Especially, a sun with at least six vertices is called a big sun. We denote by sun(G) the number of sun components of G.

Kaneko [3] posed a criterion for a graph to have a $P_{\ge 3}$-factor. Kano, Katona and Király [4] came up with a simple proof.

Theorem 1

([3, 4]). A graph G contains a $P_{\ge 3}$-factor if and only if

$$\begin{aligned} sun(G-X)\le 2|X| \end{aligned}$$

for all $X\subseteq V(G)$.

Later, Zhang and Zhou [8] extended Theorem 1, and derived a characterization for $P_{\ge 3}$-factor covered graphs.

Theorem 2

([8]). A connected graph G is a $P_{\ge 3}$-factor covered graph if and only if

$$\begin{aligned} sun(G-X)\le 2|X|-\varepsilon (X) \end{aligned}$$

for all $X\subseteq V(G)$, where $\varepsilon (X)$ is defined by

$$\begin{aligned}&\varepsilon (X)\\&\quad =\left\{ \begin{array}{ll} 2,&{}if \ X \ is \ not \ an \ independent \ set;\\ 1,&{}if \ X \ is \ a \ nonempty \ independent \ set \ and \ G-X \ has \ a \ non-sun \ component;\\ 0,&{}otherwise.\\ \end{array} \right. \end{aligned}$$

Zhou, Sun and Liu [16] introduced the sun toughness of a graph G, which is denoted by s(G) and defined by

$$\begin{aligned} s(G)=\min \left\{ \frac{|X|}{sun(G-X)}:X\subseteq V(G),sun(G-X)\ge 2\right\} \end{aligned}$$

if G is not a complete graph; otherwise, $s(G)=+\infty$. Then they showed two sun toughness conditions for graphs to be $P_{\ge 3}$-factor deleted graphs or $P_{\ge 3}$-factor covered graphs.

Theorem 3

([16]). A 2-edge-connected graph G is a $P_{\ge 3}$-factor deleted graph if its sun toughness $s(G)\ge 1$.

Theorem 4

([16]). A connected graph G of order at least 3 is a $P_{\ge 3}$-factor covered graph if its sun toughness $s(G)\ge 1$.

Zhou, Bian and Pan [12] presented a binding number condition for graphs to be $(P_{\ge 3},n)$-factor critical deleted graphs.

Theorem 5

([12]). Let n be a nonnegative integer, and let G be an $(n+2)$-connected graph. If $bind(G)>\frac{3+n}{2}$, then G is $(P_{\ge 3},n)$-critical deleted.

Zhou and Sun [14] gave a binding number condition for graphs to be $(P_{\ge 3},n)$-factor critical covered graphs.

Theorem 6

[14]. Let n be an integer with $n\ge 1$, and let G be an $(n+1)$-connected graph with $|V(G)|\ge n+3$. If $bind(G)\ge \frac{4+n}{3}$, then G is $(P_{\ge 3},n)$-factor-critical covered.

In this article, we pose sun toughness conditions for graphs to be $(P_{\ge 3},n)$-factor critical deleted graphs or $(P_{\ge 3},n)$-factor critical covered graphs, respectively. Our main results are two generalizations of Theorems 3 and 4.

Theorem 7

An $(n+r+2)$-connected graph G is a $(P_{\ge 3},n)$-factor critical deleted graph if its sun toughness $s(G)>\frac{n+r+3}{2(r+2)}$, where n and r are two nonnegative integers.

Theorem 8

An $(n+r+1)$-connected graph G is a $(P_{\ge 3},n)$-factor critical covered graph if its sun toughness $s(G)>\frac{n+r+1}{2r+1}$, where $n\ge 0$ and $r\ge 1$ are integers.

2 Proof of Theorem 7

We first show the following lemma, which will be used in the proof of Theorem 7.

Lemma 1

Let n and r be two nonnegative integers, let G be an $(n+r+2)$-connected graph, and let $H=G-Q-e$ for any $Q\subseteq V(G)$ with $|Q|=n$ and any $e\in E(G-Q)$. If $sun(H-X)\ge 2|X|+1$ for $X\subseteq V(H)$, then $|X|\ge r+2$.

Proof

Assume that $sun(H-X)\ge 2|X|+1$. Then $X\ne \emptyset$ since otherwise $G-Q$ is 2-connected and so $H=G-Q-e$ is a sun having at most two end-vertices, but every big sun has at least 3 end-vertices. Thus $\omega (G-Q-X)\ge \omega (G-Q-X-e)-1\ge sun(H-X)-1\ge 2|X|\ge 2$. Thus $|X|\ge r+2$ since G is $(n+r+2)$-connected. $\square$

Proof of Theorem 7

Theorem 7 obviously holds for a complete graph. Next, we assume that G is not a complete graph. Let $Q\subseteq V(G)$ with $|Q|=n$ and $e=uv\in E(G-Q)$, and let $H=G-Q-e$. It suffices to justify that H contains a $P_{\ge 3}$-factor. For a contradiction, suppose that H has no $P_{\ge 3}$-factor. Then by Theorem 1, there exists a vertex set X of H that satisfies

$$\begin{aligned} sun(H-X)\ge 2|X|+1. \end{aligned}$$

(1)

$\square$

Claim 1. $s(G)\le \frac{n+|X|+1}{2|X|}$.

Proof

It is obvious that

$$\begin{aligned} sun(G-Q-X-e)\le sun(G-Q-X)+2. \end{aligned}$$

Thus we prove Claim 1 by considering the following two cases.

Case 1. $sun(G-Q-X-e)\le sun(G-Q-X)+1$.

Because of (1) and Lemma 1, we obtain

$$\begin{aligned}&sun(G-Q-X)\ge sun(G-Q-X-e)-1=sun(H-X)-1\\&\quad \ge 2|X|\ge 2(r+2). \end{aligned}$$

Thus, we derive

$$\begin{aligned} s(G)\le \frac{|Q\cup X|}{sun(G-Q-X)}\le \frac{n+|X|}{2|X|}<\frac{n+|X|+1}{2|X|}. \end{aligned}$$

Case 2. $sun(G-Q-X-e)=sun(G-Q-X)+2$.

In this case, we may assume that $e=uv$ joins two sun components $D_1$ and $D_2$ of $G-Q-X-e$, where $u\in V(D_1)$ and $v\in V(D_2)$. Then it follows from (1) that $sun(G-Q-X-v)\ge sun(G-Q-X-e)-1=sun(H-X)-1\ge 2|X|\ge 2(r+2)$, which implies

$$\begin{aligned} s(G)\le \frac{|Q\cup X\cup \{v\}|}{sun(G-Q-X-v)}\le \frac{n+|X|+1}{2|X|}. \end{aligned}$$

This completes the proof of Claim 1. $\square$

Using Claim 1 and Lemma 1, we deduce

$$\begin{aligned} s(G)\le \frac{n+|X|+1}{2|X|}=\frac{1}{2}+\frac{n+1}{2|X|}\le \frac{1}{2}+\frac{n+1}{2(r+2)}=\frac{n+r+3}{2(r+2)}, \end{aligned}$$

which contradicts $s(G)>\frac{n+r+3}{2(r+2)}$. We have verified Theorem 7. $\square$

Remark 1

Now, we explain that the condition on s(G) in Theorem 7 is sharp.

Let n and r be two nonnegative integers with $n\ge r+1$, let $H_1$ and $H_2$ be two big suns, and let $G=K_{n+r+2}\vee ((2r+3)K_1\cup H_1\cup H_2\cup \{e\})$, where $e=uv$, $u\in V(H_1)$ and $v\in V(H_2)$. We know that G is $(n+r+2)$-connected and $s(G)=\frac{|V(K_{n+r+2})\cup \{v\}|}{sun(G-(V(K_{n+r+2})\cup \{v\}))}=\frac{n+r+3}{2(r+2)}$. Let $Q\subseteq V(K_{n+r+2})\subseteq V(G)$ with $|Q|=n$. Then $G-Q-e=K_{r+2}\vee ((2r+3)K_1\cup H_1\cup H_2)$. Let $X=V(K_{r+2})\subseteq V(G-Q-e)$. Then we obtain

$$\begin{aligned} sun(G-Q-e-X)=2r+5>2(r+2)=2|X|. \end{aligned}$$

From Theorem 1, $G-Q-e$ has no $P_{\ge 3}$-factor, and so G is not $(P_{\ge 3},n)$-factor critical deleted.

Remark 2

Now, we claim that the condition of $(n+r+2)$-connectedness in Theorem 7 is the best possible.

Let $G=K_{n+r+1}\vee ((2r+1)K_1\cup P_3)$, where n and r are two integers with $n-2\ge r\ge 0$. Let $P_3=x_1x_2x_3$. We know that G is $(n+r+1)$-connected and $s(G)=\frac{|V(K_{n+r+1})\cup \{x_2\}|}{sun(G-(V(K_{n+r+1})\cup \{x_2\}))}=\frac{n+r+2}{2r+3}>\frac{n+r+3}{2(r+2)}$. Let $Q\subseteq V(K_{n+r+1})\subseteq V(G)$ with $|Q|=n$ and $e\in E(P_3)$. Then $G-Q-e=K_{r+1}\vee ((2r+2)K_1\cup K_2)$. Let $X=V(K_{r+1})\subseteq V(G-Q-e)$. Then we have

$$\begin{aligned} sun(G-Q-e-X)=2r+3>2(r+1)=2|X|. \end{aligned}$$

Using Theorem 1, $G-Q-e$ has no $P_{\ge 3}$-factor, and so G is not $(P_{\ge 3},n)$-factor critical deleted.

3 The proof of Theorem 8

Proof of Theorem 8

Theorem 8 obviously holds for a complete graph. Next, we always assume that G is not complete. Let $Q\subseteq V(G)$ with $|Q|=n$, and let $H=G-Q$. It suffices to prove that H is $P_{\ge 3}$-factor covered. For a contradiction, suppose that H is not $P_{\ge 3}$-factor covered. Then by Theorem 2, we have

$$\begin{aligned} sun(H-X)\ge 2|X|-\varepsilon (X)+1 \end{aligned}$$

(2)

for some vertex set X of H.

In the following, we discuss four cases by the value of |X|.

Case 1. $|X|=0$.

Obviously, $\varepsilon (X)=0$. According to (1), $sun(H)\ge 1$. Note that G is $(n+r+1)$-connected, and so $|V(G)|\ge n+r+2$. Hence, H is $(r+1)$-connected, which implies $\omega (H)=1$. Thus, we get

$$\begin{aligned} 1\le sun(H)\le \omega (H)=1, \end{aligned}$$

namely,

$$\begin{aligned} sun(H)=\omega (H)=1. \end{aligned}$$

Combining this with $|V(H)|=|V(G)|-|Q|\ge (n+r+2)-n=r+2\ge 3$, we know that H is a big sun. Then there exists a vertex x in H such that $d_{H}(x)=1$, and so

$$\begin{aligned} d_G(x)\le d_{G-Q}(x)+|Q|=d_H(x)+n=n+1, \end{aligned}$$

which contradicts that G is $(n+r+1)$-connected.

Case 2. $|X|=1$.

In this case, $\varepsilon (X)\le 1$. In light of (1), we get

$$\begin{aligned} \omega (G-Q-X)= & {} \omega (H-X)\ge sun(H-X)\ge 2|X|\\&-\varepsilon (X)+1\ge 2|X|=2>1=\omega (G), \end{aligned}$$

which implies that G is at most $(n+1)$-connected, which contradicts that G is $(n+r+1)$-connected.

Case 3. $2\le |X|\le r$.

From (1), $\varepsilon (X)\le 2$ and $\omega (G)=1$, we derive

$$\begin{aligned} \omega (G-Q-X)= & {} \omega (H-X)\ge sun(H-X)\ge 2|X|\\&-\varepsilon (X)+1\ge 2|X|-1\ge 4-1=3>1=\omega (G), \end{aligned}$$

which implies that G is at most $(n+r)$-connected, which contradicts that G is $(n+r+1)$-connected.

Case 4. $|X|\ge r+1$.

It follows from (1), $\varepsilon (X)\le 2$ and $r\ge 1$ that

$$\begin{aligned} sun(G-Q-X)= & {} sun(H-X)\ge 2|X|-\varepsilon (X)\\&+1\ge 2|X|-1\ge 2(r+1)-1=2r+1\ge 3. \end{aligned}$$

Combining this with the definition of s(G), we infer

$$\begin{aligned} s(G)\le & {} \frac{|Q\cup X|}{sun(G-Q-X)}\le \frac{n+|X|}{2|X|-1}=\frac{1}{2}+\frac{n+\frac{1}{2}}{2|X|-1}\\\le & {} \frac{1}{2}+\frac{n+\frac{1}{2}}{2(r+1)-1}=\frac{n+r+1}{2r+1}, \end{aligned}$$

which contradicts $s(G)>\frac{n+r+1}{2r+1}$. This completes the proof of Theorem 8. $\square$

Remark 3

We now show that the condition $s(G)>\frac{n+r+1}{2r+1}$ in Theorem 8 cannot be replaced by $s(G)\ge \frac{n+r+1}{2r+1}$.

Let $G=K_{n+r+1}\vee ((2r+1)K_1)$, where $n\ge 0$ and $r\ge 1$ are two integers. We easily see that G is $(n+r+1)$-connected and $s(G)=\frac{|V(K_{n+r+1})|}{sun(G-V(K_{n+r+1}))}=\frac{n+r+1}{2r+1}$. Let $Q\subseteq V(K_{n+r+1})\subseteq V(G)$ with $|Q|=n$. Then $G-Q=K_{r+1}\vee ((2r+1)K_1)$. Select $X=V(K_{r+1})$ in $G-Q$. Then $\varepsilon (X)=2$ by the definition of $\varepsilon (X)$. Thus, we derive

$$\begin{aligned} sun(G-Q-X)=2r+1>2(r+1)-2=2|X|-\varepsilon (X). \end{aligned}$$

In light of Theorem 2, $G-Q$ is not $P_{\ge 3}$-factor covered. So G is not $(P_{\ge 3},n)$-factor critical covered.

Remark 4

We now claim that the condition of $(n+r+1)$-connectedness in Theorem 8 is sharp.

Let $G=K_{n+r}\vee ((2rK_1)\cup M)$, where $n>r\ge 1$ are two integers, and M is a connected graph not being a sun. Clearly, G is $(n+r)$-connected and $s(G)=\frac{|V(K_{n+r})|}{sun(G-V(K_{n+r}))}=\frac{n+r}{2r}>\frac{n+r+1}{2r+1}$. Let $Q\subseteq V(K_{n+r})\subseteq V(G)$ with $|Q|=n$. Then $G-Q=K_r\vee ((2rK_1)\cup M)$. Choose $X=V(K_r)$ in $G-Q$. Then $1\le \varepsilon (X)\le 2$ by the definition of $\varepsilon (X)$. Thus, we acquire

$$\begin{aligned} sun(G-Q-X)=2r>2r-1\ge 2|X|-\varepsilon (X). \end{aligned}$$

It follows from Theorem 2 that $G-Q$ is not $P_{\ge 3}$-factor covered. Hence, G is not $(P_{\ge 3},n)$-factor critical covered.