Tight toughness bounds for path-factor critical avoidable graphs

Abstract

Given a graph G and an integer $k\ge 2$, a spanning subgraph H of G is called a $P_{\ge k}$-factor of G if every component of H is a path with at least k vertices. A graph G is $P_{\ge k}$-factor avoidable if for every edge $e\in E(G)$, G has a $P_{\ge k}$-factor excluding e. A graph G is said to be $(P_{\ge k},n)$-factor critical avoidable if the graph $G-V\prime$ is $P_{\ge k}$-factor avoidable for any $V\prime \subseteq V(G)$ with $|V\prime |=n$. Here we study the sharp bounds of toughness and isolated toughness conditions for the existence of $(P_{\ge 3},n)$-factor critical avoidable graphs. In view of graph theory approaches, this paper mainly contributes to verify that (i) An $(n+2)$-connected graph is $(P_{\ge 3},n)$-factor critical avoidable if its toughness $\tau (G)>\frac{n+2}{4}$; (ii) An $(n+2)$-connected graph is $(P_{\ge 3},n)$-factor critical avoidable if its isolated toughness $I(G)>\frac{n+6}{4}$.

Keywords:

• Graph
• path-factor
• toughness
• isolated toughness
• $(P_{\ge 3},n)$-factor critical avoidable graph

Mathematics Subject Classification:

• 05C38
• 05C70

1 Introduction

All graphs considered here are finite and simple. We refer to [3] for the notations and terminologies not defined here. Let G be a graph with vertex set V(G) and edge set E(G). Given a vertex $v\in V(G)$, let $d_G(v)$ denote the degree of v. If $d_G(v)=0$ for some vertex v in G, then v is said to be an isolated vertex in G. Let i(G) be the number of isolated vertices of G. For any subset $S\subseteq V(G)$, let $G[S]$ denote the subgraph of G induced by S, and $G-S:=G[V(G)\setminus S]$ is the resulting graph after deleting the vertices of S from G. The number of connected components of a graph G is denoted by $\omega (G)$. We write $\kappa (G)$ for the vertex connectivity of G.

A subgraph H of G is called a spanning subgraph of G if $V(H)=V(G)$ and $E(H)\subseteq E(G)$. For a family of connected graphs $\mathcal{F}$, a spanning subgraph H of a graph G is called an $\mathcal{F}$-factor of G if each component of H is isomorphic to some graph in $\mathcal{F}$. A spanning subgraph H of a graph G is called a $P_{\ge k}$-factor of G if every component of H is isomorphic to a path of order at least k, where $k\ge 2$ is an integer. For example, a $P_{\ge 3}$-factor means a graph factor in which every component is a path of order at least three. Since Tutte proposed the well known Tutte 1-factor theorem [16], there are many results on graph factors [2, 4, 6, 8, 9, 11, 12, 14, 15, 17, 18, 23, 26] and factor covered graphs [7, 10, 20, 22, 25, 27]. More results on graph factors of graphs refer to the books [1, 21].

In order to characterize a graph possessing a $P_{\ge 3}$-factor, Kaneko [13] put forward the concept of a sun as follows. A graph R is called factor-critical if R – v has a 1-factor for each $v\in V(R)$. Let R be a factor-critical graph and $V(R)=\{v_1,v_2,\dots ,v_n\}$. By adding new vertices $\{u_1,u_2,\dots ,u_n\}$ together with new edges $\{v_i{u}_i:1\le i\le n\}$ to R, the resulting graph is called a sun. Note that, according to Kaneko [13], we regard K₁ and K₂ also as a sun, respectively. Usually, the suns other than K₁ and K₂ are also called big suns. It is called a sun component of G if the component of G is isomorphic to a sun. We denote by sun(G) the number of sun components in G.

Theorem 1.1.

(Kaneko [13]) A graph G has a $P_{\ge 3}$-factor if and only if $\mathit{\text{sun}}(G-X)\le 2\left|X\right|$ for all $X\subseteq V(G)$.

Next, we introduce two parameters for a graph, namely, toughness and isolated toughness. The toughness of G was first introduced by Chvátal [5] as $$\tau (G)=\mathrm{\text{min}}\left\{\frac{\left|X\right|}{\omega (G-X)}:X\subseteq V(G),\omega (G-X)\ge 2\right\},$$ if G is not complete; otherwise, $\tau (G)=+\infty$. The isolated toughness of G was defined by Yang et al. in [19] as $$I(G)=\mathrm{\text{min}}\left\{\frac{\left|X\right|}{i(G-X)}:X\subseteq V(G),i(G-X)\ge 2\right\},$$ if G is not complete; otherwise, $I(G)=+\infty$.

A graph G is $P_{\ge k}$-factor avoidable if for every edge $e\in E(G)$, G has a $P_{\ge k}$-factor that excludes e. A graph G is $(P_{\ge k},n)$-factor critical avoidable if for any subset $V\prime \subseteq V(G)$ with $|V\prime |=n$, the graph $G-V\prime$ is $P_{\ge k}$-factor avoidable. More recently, Zhou [24] explored the relationship between toughness (resp. isolated toughness) and $(P_{\ge k},n)$-factor critical avoidable graphs. In the same paper, they gave toughness and isolated toughness conditions for $(P_{\ge 3},n)$-factor critical avoidable graphs, respectively. However, we find the toughness bound and isolated toughness bound obtained by Zhou [24] are not sharp and have a lot of space to improve them.

Inspired by finding the sharpness bounds, in this study, we continue to study the relationship between different graph parameters and the existence of $(P_{\ge 3},n)$-factor critical avoidable graphs. Our main results are listed as follows which will be proved in the next section. Note that the conditions in Theorem 1.2 and 1.3 are sharp, which improve the results of Zhou [24].

Theorem 1.2.

Let G be an $(n+2)$-connected graph, where $n\ge 0$ is an integer. If its toughness $\tau (G)>\frac{n+2}{4}$, then G is a $(P_{\ge 3},n)$-factor critical avoidable graph.

Theorem 1.3.

Let G be an $(n+2)$-connected graph, where n is a positive integer. If its isolated toughness $I(G)>\frac{n+6}{4}$, then G is a $(P_{\ge 3},n)$-factor critical avoidable graph.

2 Proof of main results

Our goal in this section is to present the detailed proofs of main theorems. Additionally, we will use some examples to explain all the conditions in Theorems 1.2 and 1.3 are best possible in some sense.

2.1 Proof of Theorem 1.2

If G is a complete graph, then it is easily seen that G is a $(P_{\ge 3},n)$-factor critical avoidable graph by $\kappa (G)\ge n+2$. Next, we consider that G is a non-complete graph. For any $V\prime \subseteq V(G)$ with $|V\prime |=n$, we write $G\prime =G-V\prime$. To verify Theorem 1.2, it suffices to prove that $H:=G\prime -e$ contains a $P_{\ge 3}$-factor for any $e=\mathit{\text{xy}}\in E(G\prime )$. On the contrary, we assume that H has no $P_{\ge 3}$-factor. Then by Theorem 1.1, there exists a subset $X\subseteq V(H)$ such that $\mathit{\text{sun}}(H-X)>2\left|X\right|$. In terms of the integrality of $\mathit{\text{sun}}(H-X)$, we obtain that (1) $$\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1.$$(1)

Claim 2.1. $X\ne \varnothing$.

Proof.

On the contrary, we assume that $X=\varnothing$. It follows from (1) that (2) $$\mathit{\text{sun}}(H)=\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1=1.$$(2)

Note that H is connected with at least three vertices since $\kappa (H)\ge \kappa (G)-|V\prime |-1\ge 1$. Combining this with (2), we have $1\le \mathit{\text{sun}}(H)\le \omega (H)=1$, that is, (3) $$\mathit{\text{sun}}(H)=\omega (H)=1.$$(3)

It follows from (3) that H is a big sun, and $|V(H)|\ge 6$. Let R be the factor-critical graph of H. Then $|V(R)|\ge 3$ and there exists $w\in V(R)$ such that $\omega (G\prime -\{w\})=\omega (H-\{w\})=2$. Obviously, w is a cut-vertex of $G\prime$, which is a contradiction since $\kappa (G\prime )\ge \kappa (G)-|V\prime |\ge 2$. Hence, Claim 2.1 is verified. □

Claim 2.2. $\left|X\right|\ge 2$.

Proof.

On the contrary, by Claim 2.1, we assume that $\left|X\right|=1$. Since G is $(n+2)$-connected, $\kappa (G\prime )\ge \kappa (G)-n=2$. It follows that $G\prime -X$ is a connected graph, i.e., $\omega (G\prime -X)=1$. Then by the definition of H, we have that (4) $$\omega (H-X)=\omega (G\prime -X-e)\le \omega (G\prime -X)+1=2.$$(4)

On the other hand, according to (1), $$\omega (H-X)\ge \mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1\ge 3,$$

which is a contradiction to (4). Hence, Claim 2.2 is verified. □

It follows immediately from (1) and Claim 2.2 that $\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1\ge 5$. Then, we obtain that $$\begin{array}{c}\omega (G-(V\prime \cup X))=\omega (G\prime -X)\ge \omega (G\prime -X-e)-1\\ =\omega (H-X)-1\ge \mathit{\text{sun}}(H-X)-1\ge 4.\end{array}$$

Combining this with (1), Claim 2.2 and the definition of $\tau (G)$, we have $$\begin{array}{c}\tau (G)\le \frac{|V\prime \cup X|}{\omega (G-(V\prime \cup X))}\le \frac{n+\left|X\right|}{\mathit{\text{sun}}(H-X)-1}\\ \le \frac{n+\left|X\right|}{2\left|X\right|}\le \frac{1}{2}+\frac{n}{2\left|X\right|}\le \frac{1}{2}+\frac{n}{4}=\frac{n+2}{4},\end{array}$$ which contradicts that $\tau (G)>\frac{n+2}{4}$ in Theorem 1.2.

Remark 2.1.

Next, we show that the toughness condition $\tau (G)>\frac{n+2}{4}$ in Theorem 1.2 is sharp. We construct a graph $G=K_{n+2}\vee (4K_2)$. Then it is easily seen that $\tau (G)=\frac{n+2}{4}$ and $\kappa (G)=n+2$. Set $e\in E(4K_2),V\prime \subseteq V(K_{n+2})$ with $|V\prime |=n$. Let $G\prime =G-V\prime$ and $H=G\prime -e$. For $X=V(K_{n+2})\setminus V\prime$, we admit $\mathit{\text{sun}}(H-X)=5>4=2\left|X\right|.$ According to Theorem 1.1, H does not contain $P_{\ge 3}$-factor. Hence, $G\prime$ is not a $P_{\ge 3}$-factor avoidable graph. Combining this with $G\prime =G-V\prime$, G is not a $(P_{\ge 3},n)$-factor critical avoidable graph.

2.2 Proof of Theorem 1.3

Theorem 1.3 obviously holds for a complete graph. Next, we assume that G is not complete. Let $V\prime \subseteq V(G)$ with $|V\prime |=n$, and $G\prime =G-V\prime$. Let $e=\mathit{\text{xy}}\in E(G\prime )$ and $H=G\prime -e$. Since G is $(n+2)$-connected, thus H is connected. To prove Theorem 1.3, it suffices to show that H admits a $P_{\ge 3}$-factor. On the contrary, suppose that H has no $P_{\ge 3}$-factor. Then by Theorem 1.1, there exists a subset $X\subseteq V(H)$ such that (5) $$\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1.$$(5)

Claim 2.3. $X\ne \varnothing$.

Proof.

Assume $X=\varnothing$. Then by (5), we have that (6) $$\mathit{\text{sun}}(H)=\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1=1.$$(6)

Note that H is connected with at least three vertices since $\kappa (H)\ge \kappa (G)-|V\prime |-1\ge 1$. This together with (6) implies $\mathit{\text{sun}}(H)=\omega (H)=1$. It follows that H is a big sun with $|V(H)|\ge 6$. Let R be the factor-critical graph of H, then $i(H-V(R))=|V(R)|\ge 3$, and thus $G\prime =H+e$ has a vertex with degree one. This is a contradiction, since $\kappa (G\prime )\ge \kappa (G)-|V\prime |\ge 2$. Hence, Claim 2.3 holds. □

Claim 2.4. $\left|X\right|\ge 2$.

Proof.

On the contrary, by Claim 2.3, we assume that $\left|X\right|=1$. Since G is $(n+2)$-connected, $\kappa (G\prime )\ge \kappa (G)-n=2$. It follows that $G\prime -X$ is a connected graph, i.e., $\omega (G\prime -X)=1$. Then by the definition of H, we have that (7) $$\omega (H-X)=\omega (G\prime -X-e)\le \omega (G\prime -X)+1=2.$$(7)

On the other hand, according to (5), $$\omega (H-X)\ge \mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1\ge 3,$$

which is contradiction to (7). Hence, Claim 2.4 is verified. □

Let $\mathit{\text{Sun}}(H-X)$ denote the union of sun components of H – X, which consists of a isolated vertices, b K₂-components and c big sun components $S_1,S_2,\dots ,S_c$. Let R_i be the factor-critical subgraph of S_i for $1\le i\le c$, and write $Z={\cup }_{i=1}^{c}V(R_i)$. We select one vertex from every K₂ component of H – X, and the set of such vertices is denoted by Y. Clearly, $\left|Y\right|=b$. Then $i(H-(X\cup Y\cup Z))=a+b+\left|Z\right|$ and it follows from (5) and Claim 2.3 that (8) $$a+b+c=\mathit{\text{sun}}(H-X)\ge 2\left|X\right|+1\ge 5.$$(8)

Claim 2.5. $x,y\notin V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c)$.

Proof.

On the contrary, without loss of generality, we assume that $x\in V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c)$. Then there exists $z\in V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c)$ such that $\mathit{\text{xz}}\in E(G)$ and there is at least one vertex of {x, z} with degree one in the subgraph $b{K}_2\cup S_1\cup \cdots \cup S_c$. Thus, we obtain (9) $$i(G-(V\prime \cup X\cup (Y\cup Z\setminus \{z\})\cup \left\{x\right\}))=a+b+3c\ge 5$$(9) by (8), $c\ge 0$ and $\left|Z\right|\ge 3c$. Combining(9) with the definition of I(G) and $I(G)>\frac{n+6}{4}$, we obtain $$\begin{array}{c}\frac{n+6}{4}<I(G)\le \frac{|V\prime \cup X\cup (Y\cup Z\setminus \left\{z\right\})\cup \{x\left\}\right|}{i(G-(V\prime \cup X\cup (Y\cup Z\setminus \{z\})\cup \left\{x\right\}))}\\ \le \frac{n+\left|X\right|+b+\left|Z\right|}{a+b+\left|Z\right|}\\ \le 1+\frac{n+\left|X\right|}{a+b+\left|Z\right|}\\ \le 1+\frac{n+\left|X\right|}{a+b+c}\\ \le 1+\frac{1}{2}+\frac{n}{a+b+c}\\ \le \frac{3}{2}+\frac{n}{5}=\frac{2n+15}{10},\end{array}$$

which is a contradiction. Hence, Claim 2.5 is verified. □

Claim 2.6. $0\le a\le 1$.

Proof.

On the contrary, we assume that $a\ge 2$. In terms of (8), $c\ge 0$ and $|V(R_i)|\ge 3$, we obtain $$\begin{array}{c}i(G‐\mathrm{}(V\prime \cup X\cup Y\cup Z\cup \left\{x\right\}))=i(G\prime ‐\mathrm{}(X\cup Y\cup Z\cup \left\{x\right\})‐\mathrm{}e)\\ =i(H-(X\cup Y\cup Z\cup \left\{x\right\}))\\ \ge i(H-(X\cup Y\cup Z))-1\\ =a+b+\left|Z\right|-1\\ \ge a+b+c-1\ge 4.\end{array}$$

Combining this with (8), $a\ge 2,c\ge 0$ and the definition of I(G), we derive $$\begin{array}{c}\frac{n+6}{4}<I(G)\le \frac{|V\prime \cup X\cup Y\cup Z\cup \{x\left\}\right|}{i(G-(V\prime \cup X\cup Y\cup Z\cup \left\{x\right\}))}\\ \le \frac{n+\left|X\right|+b+\left|Z\right|+1}{a+b+\left|Z\right|-1}\\ \le 1+\frac{n+\left|X\right|+2-a}{a+b+\left|Z\right|-1}\\ \le 1+\frac{n+\left|X\right|}{a+b+c-1}\\ \le 1+\frac{1}{2}+\frac{n}{a+b+c-1}\\ \le 1+\frac{1}{2}+\frac{n}{4}=\frac{n+6}{4},\end{array}$$

which is a contradiction. Hence, Claim 2.6 holds. □

By Claim 2.6, we easily see that $x\notin V(a{K}_1)$ or $y\notin V(a{K}_1)$ since $0\le a\le 1$. This together with Claim 2.5 implies that there is at least one vertex in {x, y} such that the vertex does not belong $V(a{K}_1)\cup V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c)$. Without loss of generality, we let $x\notin V(a{K}_1)\cup V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c)$, then $x\in V(G)\setminus (V\prime \cup V(a{K}_1)\cup V(b{K}_2)\cup V(S_1)\cup \cdots \cup V(S_c))$. Next, we will distinguish two cases below to complete the proof of Theorem 1.3.

Case 1.

$y\notin V(a{K}_1)$.

In terms of (8), $c\ge 0$ and $\left|Z\right|\ge 3c$, we can easily deduce that (10) $$i(G-(V\prime \cup X\cup Y\cup Z))\ge a+b+\left|Z\right|\ge a+b+3c\ge 5.$$(10)

Combining this with (10) and the definition of I(G), we derive (11) $$I(G)\le \frac{|V\prime \cup X\cup Y\cup Z|}{i(G-(V\prime \cup X\cup Y\cup Z))}\le \frac{n+\left|X\right|+b+\left|Z\right|}{a+b+\left|Z\right|}.$$(11)

It follows from (8), (11), $a\ge 0,c\ge 0,\left|Z\right|\ge 3c$ and $I(G)>\frac{n+6}{4}$ that $$\begin{array}{c}0\ge (I(G)-1)(a+b+|Z|)+a-n-\left|X\right|\\ \ge (I(G)-1)(a+b+3c)-n-\left|X\right|\\ \ge (I(G)-1)(a+b+c)-n-\left|X\right|\\ \ge (I(G)-1)(2|X|+1)-n-\left|X\right|\\ =(2|X|+1)I(G)-n-3\left|X\right|-1,\end{array}$$ which implies (12) $$I(G)\le \frac{3\left|X\right|+n+1}{2\left|X\right|+1}.$$(12)

In terms of (12), $n\ge 1$ and $\left|X\right|\ge 2$, we have $$I(G)\le \frac{3\left|X\right|+n+1}{2\left|X\right|+1}=\frac{3}{2}+\frac{n-\frac{1}{2}}{2\left|X\right|+1}\le \frac{3}{2}+\frac{n-\frac{1}{2}}{5}=\frac{n+7}{5},$$ which contradicts $I(G)>\frac{n+6}{4}$.

Case 2.

$y\in V(a{K}_1)$.

In this case, $a\ge 1$. In terms of (8), $c\ge 0$ and $\left|Z\right|\ge 3c$, we can derive that (13) $$i(G-(V\prime \cup X\cup Y\cup Z\cup \left\{x\right\}))\ge a+b+\left|Z\right|\ge a+b+3c\ge 5.$$(13)

According to (13) and the definition of I(G), we derive (14) $$I(G)\le \frac{|V\prime \cup X\cup Y\cup Z\cup \{x\left\}\right|}{i(G-(V\prime \cup X\cup Y\cup Z\left\{x\right\}))}\le \frac{n+\left|X\right|+b+\left|Z\right|+1}{a+b+\left|Z\right|}.$$(14)

It follows from (8), (14), $a\ge 1,c\ge 0,\left|Z\right|\ge 3c,\left|X\right|\ge 2$ and $I(G)>\frac{n+6}{4}$ that $$\begin{array}{c}\frac{n+6}{4}<I(G)\le \frac{n+\left|X\right|+b+\left|Z\right|+1}{a+b+\left|Z\right|}\\ =1+\frac{n+\left|X\right|+1-a}{a+b+\left|Z\right|}\\ \le 1+\frac{n+\left|X\right|}{a+b+3c}\\ \le 1+\frac{n+\frac{a+b+c-1}{2}}{a+b+c}\\ \le 1+\frac{1}{2}+\frac{n-\frac{1}{2}}{a+b+c}\\ \le \frac{3}{2}+\frac{n-\frac{1}{2}}{5}=\frac{n+7}{5},\end{array}$$ which is a contradiction.

This finishes the proof of Theorem 1.3.

Remark 2.2.

The isolated toughness condition $I(G)>\frac{n+6}{4}$ in Theorem 1.3 is sharp. We construct a graph $G=K_{n+2}\vee (4K_2)$. Then it is easily seen that $I(G)=\frac{n+6}{4}$ and $\kappa (G)=n+2$. Set $e\in E(4K_2),V\prime \subseteq V(K_{n+2})$ with $|V\prime |=n$. Let $H=G-V\prime -e$. For $X=V(K_{n+2})\setminus V\prime$, we admit $\mathit{\text{sun}}(H-X)=5>4=2\left|X\right|.$ According to Theorem 1.1, H does not contain $P_{\ge 3}$-factor. Hence, G is not a $(P_{\ge 3},n)$-factor critical avoidable graph.

Additional information

Funding

This work was supported by Natural Science Foundation of Jiangsu Province (No. BK20230388) and National Natural Science Foundation of China (No. 12301441).