# Tight Toughness and Isolated Toughness for $\\{K_{2},C_{n}\\}$-factor
critical avoidable graph

Xiaxia Guanb 111E-mail<EMAIL_ADDRESS>Hongxia Ma b,c
222Corresponding author. E-mail<EMAIL_ADDRESS>Maoqun Wangd 333E-mail:
<EMAIL_ADDRESS>
$~{}^{a}$ Department of Mathematics, Taiyuan University of Technology,
Taiyuan 030024, PR China
$~{}^{b}$ School of Mathematical Sciences, Xiamen University,
Xiamen 361000, PR China
$~{}^{c}$ School of Mathematical Sciences, Xinjiang Normal University,
Urumqi 830053, PR China
$~{}^{d}$ School of Mathematics and Information Sciences, Yantai University,
Yantai 264005, PR China

###### Abstract

A spannning subgraph $F$ of $G$ is a $\\{K_{2},C_{n}\\}$-factor if each
component of $F$ is either $K_{2}$ or $C_{n}$. A graph $G$ is called a
$(\\{K_{2},C_{n}\\},n)$-factor critical avoidable graph if $G-X-e$ has a
$\\{K_{2},C_{n}\\}$-factor for any $S\subseteq V(G)$ with $|X|=n$ and $e\in
E(G-X)$. In this paper, we first obtain a sufficient condition with regard to
isolated toughness of a graph $G$ such that $G$ is $\\{K_{2},C_{n}\\}$-factor
critical avoidable. In addition, we give a sufficient condition with regard to
tight toughness and isolated toughness of a graph $G$ such that $G$ is
$\\{K_{2},C_{2i+1}|i\geqslant 2\\}$-factor critical avoidable respectively.

###### keywords:

Factor, Component factor, Toughness, Isolated Toughness , Factor avoidable
graph

###### MSC:

05C70, 05C38, 90B10

##  1 Introduction

Given a graph $G$, let $V(G)$ and $E(G)$ denote the sets of vertices and edges
of $G$, respectively. For $S\subseteq V(G)$, we use $G-S$ to denote the
subgraph of $G$ induced by the set $V(G)\setminus S$. For $E^{\prime}\subseteq
E(G)$, we use $G-E^{\prime}$ to denote the subgraph of $G$ by deleting all
edges in $E^{\prime}$. In particular we write $G-e$ for $G-E^{\prime}$ if
$E^{\prime}=\\{e\\}$. For $X\subseteq V(G)$, let $c(G-X)$ and $i(G-X)$ denote
the numbers of components and isolated vertices in $G-X$, respectively. All
graphs considered in this paper are simple, finite and undirected.

Chvátal [1] introduced the _toughness_ of a graph $G$, denoted by $t(G)$, as
follows: $t(G)=+\infty$ if $G$ is complete; otherwise

$t(G)=\min\left\\{\frac{|S|}{c(G-S)}\ \bigg{|}\ S\subseteq V(G),c(G-S)\geq
2\right\\}.$

Yang, Ma and Liu [4] introduced the _isolated toughness_ of a graph $G$,
denoted by $I(G)$, as follows: $I(G)=+\infty$ if $G$ is complete; otherwise,

$I(G)=\min\left\\{\frac{|S|}{iso(G-S)}\ \bigg{|}\ S\subseteq V(G),i(G-S)\geq
2\right\\}.$

Let $\mathcal{F}$ be a family of graphs. Let $G$ be a graph and let $F$ be a
spannning subgraph of $G$. We call that $F$ is an $\mathcal{F}$-_factor_ if
each component of $F$ is an element of $\mathcal{F}$, we also say that $G$
contains an $\mathcal{F}$-factor.

A graph $G$ is called to be $\mathcal{F}$-factor avoidable if $G-e$ has a
$\mathcal{F}$-factor for any $e\in E(G)$. A graph $G$ is called to be
$(\mathcal{F},n)$-_factor critical avoidable_ if $G-S$ is $\mathcal{F}$-factor
avoidable for any $S\subseteq V(G)$ with $|S|=n$, that is, $G-S-e$ contains an
$\mathcal{F}$-factor for any $e\in E(G-S)$.

Let $P_{\geq k}$ denote a family of paths with at least $k$ vertices. Zhou et
al. [5] otained some conditions on binding number of a graph $G$ such that $G$
is $(P_{\geq k},n)$-factor critical avoidable for $k=2,3$. In [6], Zhou et al.
gave a condition on sun toughness of a graph $G$ such that $G$ is $(P_{\geq
3},n)$-factor critical avoidable. Recently, Zhou and Liu [7] gave a condition
on toughness and isolated toughness of a graph $G$ such that $G$ is $(P_{\geq
k},n)$-factor critical avoidable.

Let $\\{K_{2},C_{n}\\}$ denote a family of paths with $2$ vertices and cycles
with at least $n$ vertices. In this paper, we first obtain a sufficient
condition with regard to isolated toughness of a graph $G$ such that $G$ is
$\\{K_{2},C_{n}\\}$-factor critical avoidable.

######  Theorem 1.1.

For two nonnegative integers $n$ and $k$, let $G$ be $(n+k+3)$-connected. If
its isolated toughness $I(G)>\frac{n+k+4}{k+3}$, then $G$ is a
$\\{K_{2},C_{n}\\}$-factor critical avoidable graph.

Note that if some component of a subgraph $F$ has a cycle of the length $2k$,
then there is a subgraph $k$’$K_{2}$ in this component. Hence, it is enough to
consider the cycles whose the length is odd. In addition, we give a sufficient
condition with regard to tight toughness and isolated toughness of a graph $G$
such that $G$ is $\\{K_{2},C_{2i+1}|i\geqslant 2\\}$-factor critical
avoidable, respectively.

######  Theorem 1.2.

For two nonnegative integers $n$ and $k$, let $G$ be $(n+k+3)$-connected. If
its toughness $t(G)>\frac{n+k+4}{k+3}$ or its isolated toughness
$I(G)>\frac{3(k+3)+n-1}{k+3}$, then $G$ is a $\\{K_{2},C_{n}|n\geq
5\\}$-factor critical avoidable graph.

In Section 2, we shall give the proof of Theorem 1.1. In Section 3, we shall
prove Theorem 1.2. Some classes of graphs are constructed to demonstrate the
tightness for the bounds our obtain in the following two sections
respectively.

##  2  Proof of Theorem 1.1

In this section, we give a proof of Theorem 1.1. We start with a result from
[3].

######  Theorem 2.1.

[3] A graph $G$ admits a $\\{K_{2},C_{n}\\}$-factor if and only if
$i(G-X)\leq|X|$ for any $X\subset V(G)$.

_Proof of of Theorem 1.1._ It is easy to see that it is true for a complete
graph. We next assume that $G$ is not complete. For any $W\subset V(G)$ with
$|W|=n$ and any edge $e\in E(G-W)$, let $H=G-W-e$. We next prove that $H$
admits a $\\{K_{2},C_{n}\\}$-factor. On the contrary, we assume that $H$ does
not admit a $\\{K_{2},C_{n}\\}$-factor. Then

$i(H-X)\geq|X|+1$ (1)

for some subset $X\subset V(H)$ by Theorem 2.1.

Note that $G$ is $(n+k+3)$-connected. Then $H$ is $(k+2)$-connected.

Claim 1. $|X|\geq k+3$.

Note that $H$ is $(k+2)$-connected. We have that $|V(H)|\geq k+2\geq 2$ and
$w(H)=1$. If $X=\emptyset$, then $1=w(H)\geq i(H)\geq 1$, that is, $i(H)=1$
and $V(H)=1$, which contradicts that $|V(H)|\geq 2$.

If $X=\\{u\\}$, then $|X|=1$ and $i(H-\\{u\\})\geq 2$ from (1), which again
contradicts that $H$ is a $(k+2)$-connected graph.

Assume that $2\leq|X|\leq k+2$. Then $i(H-X)\geq|X|+1\geq 3$ from (1). So,

$i(G-W-X)\geq i(G-W-e-X)-2=i(H-X)-2\geq|X|+1-2\geq 1.$

This implies that there is an isolated vertex $v\in V(G-W-X)$ in the subgraph
$G-W-X$, i.e., $d_{G-W-X}(v)=0$. Thus

$d_{G}(v)\leq d_{G-W-X}(v)+|W|+|X|\leq 0+n+k+2\leq n+k+2$

as $|W|=n$ and $|X|\leq k+2$. This is a contradiction since $G$ is
$(n+k+3)$-connected.

Hence, $|X|\geq k+3$, Claim 1 is verified.

Claim 2. $I(G)\leq\frac{n+k+4}{k+3}$.

It is clear that $i(G-W-e-X)\geq i(G-W-X)\geq i(G-W-e-X)-2$ for any edge
$e=uv$. We next distinguish three cases below to prove Claim 2.

Case 1. $i(G-W-X)=i(G-W-X-e)$.

In this case, $d_{G-W-X}(u)>1$ and $d_{G-W-X}(v)>1$, that is, neither $u$ nor
$v$ is an isolated vertex in $H-X$. We have that

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup
X}{i(G-W-X)}$ $\displaystyle=$ $\displaystyle\frac{n+|X|}{i(G-W-X-e)}$
$\displaystyle=$ $\displaystyle\frac{n+|X|}{i(H-X)}$ $\displaystyle\leq$
$\displaystyle\frac{n+|X|}{|X|+1}$ $\displaystyle=$ $\displaystyle
1+\frac{n-1}{|X|+1}$

from (1).

If $n\leq 1$, i.e., $n-1\leq 0$, then

$I(G)\leq 1<\frac{k+4}{k+3}.$

If $n\geq 2$, then

$I(G)\leq 1+\frac{n-1}{|X|+1}\leq
1+\frac{n-1}{k+3+1}=\frac{n+k+3}{k+4}<\frac{n+k+4}{k+3}$

from Claim 1.

Case 2. $i(G-W-X)=i(G-W-X-e)-1$.

In this case, there is a vertex $v$ with $d_{G-W-X}(v)=1$. Assume that $u$ is
the unique vertex adjacent to $v$ in the subgraph $G-W-X$. Then by (1) and
Claim 1, we have that

$\displaystyle i(G-W-X-u)$ $\displaystyle=$ $\displaystyle i(G-W-X)+1$
$\displaystyle=$ $\displaystyle i(G-W-X-e)-1+1$ $\displaystyle=$
$\displaystyle i(H-X)$ $\displaystyle\geq$ $\displaystyle|X|+1$
$\displaystyle\geq$ $\displaystyle r+4.$

Thus,

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup
X\cup\\{u\\}}{i(G-W-X-u)}$ $\displaystyle\leq$
$\displaystyle\frac{n+|X|+1}{|X|+1}$ $\displaystyle=$ $\displaystyle
1+\frac{n}{|X|+1}$ $\displaystyle\leq$ $\displaystyle 1+\frac{n}{k+4}$
$\displaystyle=$ $\displaystyle\frac{n+k+4}{k+4}$ $\displaystyle<$
$\displaystyle\frac{n+k+4}{k+3}.$

Case 3. $i(G-W-X)=i(G-W-X-e)-2$.

In this case, there is a $K_{2}$ component in the subgraph $G-W-X$ with
$e=E(K_{2})$. Then by (1) and Claim 1, we have that

$\displaystyle i(G-W-X-u)$ $\displaystyle=$ $\displaystyle i(G-W-X)+1$
$\displaystyle=$ $\displaystyle i(G-W-X-e)-2+1$ $\displaystyle=$
$\displaystyle i(H-X)-1$ $\displaystyle\geq$ $\displaystyle|X|$
$\displaystyle\geq$ $\displaystyle r+3.$

Thus,

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup
X\cup\\{u\\}}{i(G-W-X-u)}$ $\displaystyle=$ $\displaystyle\frac{n+|X|+1}{|X|}$
$\displaystyle=$ $\displaystyle 1+\frac{n}{|X|}$ $\displaystyle\leq$
$\displaystyle 1+\frac{n}{r+3}$ $\displaystyle=$
$\displaystyle\frac{n+k+4}{k+3}.$

Hence, Claim 2 is verified. This is a contradiction since
$I(G)>\frac{n+k+4}{k+3}$. This implies that $G$ is $\\{K_{2},C_{n}\\}$-factor
critical avoidable.

######  Remark 2.2.

If $G$ is $(n+k+3)$-connected, then $I(G)>\frac{n+k+4}{k+3}$ in Theorem 1.1 is
best possible.

For two nonnegative integers $n$ and $k$ with $n\geq k+1$, let
$G=K_{n+k+3}+((k+2)K_{1}\cup K_{2})$. It is easy to see that $G$ is
$(n+k+3)$-connected and $I(G)=\frac{n+k+4}{k+3}$. Assume that $W\subset
V(K_{n+k+3})\subset V(G)$ with $|W|=n$ and $e=E(K_{2})$. Then
$G-W-e=K_{k+3}+((k+4)K_{1})$. Let $X=V(K_{k+3})$ in the subgraph $G-W-e$. Then
$i(G-W-e-X)=k+4>k+3=|X|$. This implies that $G$ is not a
$\\{K_{2},C_{n}\\}$-factor critical avoidable graph by Theorem 2.1.

######  Remark 2.3.

The condition on $(n+k+3)$-connected of Theorem 1.1 is best possible.

For two nonnegative integers $n$ and $k$ with $n\geq k+1$, let
$G=K_{n+k+2}+((k+1)K_{1}\cup K_{2})$. It is easy to see that $G$ is a
$(n+k+2)$-connected graph and $I(G)=\frac{n+k+3}{k+2}>\frac{n+k+4}{k+3}$.
Assume that $W\subset V(K_{n+k+2})\subset V(G)$ with $|W|=n$ and $e=E(K_{2})$.
Then $G-W-e=K_{k+2}+((k+3)K_{1})$. Let $X=V(K_{k+2})$ in the subgraph $G-W-e$.
Then $i(G-W-e-X)=k+3>k+2=|X|$. This implies that $G$ is not a
$\\{K_{2},C_{n}\\}$-factor critical avoidable graph by Theorem 2.1.

##  3 Proof of Theorem 1.2

In this section, we give a proof of Theorem 1.2.

A connected graph $G$ is called _triangular-cactus_ if each block of $G$ is a
triangle. It is obvious that $K_{3}$ is a triangular-cactus. We also say that
$K_{1}$ is a triangular-cactus. For a graph $G$, its the number of triangular-
cacti components is denoted by $c_{tc}(G)$. We start with a result from [2].

######  Theorem 3.1.

[2] A graph $G$ admits a $\\{K_{2},C_{2i+1}|i\geq 2\\}$-factor if and only if
$c_{tc}(G-X)\leq|X|$ for any $X\subset V(G)$.

_Proof of Theorem 1.2._ It is easy to see that it is true for a complete
graph. We next assume that $G$ is not complete. For any $W\subset V(G)$ with
$|W|=n$ and any edge $e\in E(G-w)$, let $H=G-W-e$. It is enough to prove that
$H$ admits a $\\{K_{2},C_{2i+1}|i\geq 2\\}$-factor. On the contrary, we assume
that $H$ does not admit a $\\{K_{2},C_{2i+1}|i\geq 2\\}$-factor. Then

$c_{tc}(H-X)\geq|X|+1$ (2)

for some subset $X\subset V(H)$ by Theorem 3.1.

Claim 1. $|X|\geq k+3$.

It is obvious that $G-W-e$ is not a complete graph. If $X=\emptyset$, then
$c_{tc}(G-W-e)\geq 1$. Note that $1=w(G-W-e)\geq c_{tc}(G-W-e)\geq 1$ since
$G-W-e$ is $(k+2)\geq 2$-connected. We have that $w(G-W-e)=1$. It is easy to
see that $G-W-e$ is a block, otherwise, which contradicts that $G-W-e$ is
$2$-connected. So, $G-W-e$ is a triangle, which contradicts that $G-W-e$ is
not a complete graph.

If $X=\\{u\\}$, then $|X|=1$ and $c_{tc}(G-W-e-\\{u\\})\geq 2$. Note that
$w(G-W-e-\\{u\\})\geq c_{tc}(G-W-e-\\{u\\})\geq 2$. This contradicts that
$G-W-e$ is a $(k+2)$-connected graph.

Assume that $2\leq|X|\leq k+2$. Then $w(G-w-e-X)\geq c_{tc}(G-w-
e-X)\geq|X|+1\geq 3$. So,

$w(G-W-X)\geq w(G-W-e-X)-1\geq 2,$

that is, $G-W-X$ is not connected. Note that $|W\cup X|=|W|+|X|\leq n+k+2$.
This is a a contradiction since $G$ is $(n+k+3)$-connected.

Hence, $|X|\geq k+3$.

Claim 2. $t(G)\leq\frac{n+k+4}{k+3}$.

By (2) and Claim 1, we have that

$\displaystyle w(G-W-X)$ $\displaystyle\geq$ $\displaystyle w(G-W-X-e)-1$
$\displaystyle=$ $\displaystyle w(H-X)-1$ $\displaystyle\geq$ $\displaystyle
c_{tc}(H-X)-1$ $\displaystyle\geq$ $\displaystyle|X|$ $\displaystyle\geq$
$\displaystyle r+3.$

Thus,

$\displaystyle t(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup
X}{w(G-W-X)}$ $\displaystyle=$ $\displaystyle\frac{n+|X|}{|X|}$
$\displaystyle=$ $\displaystyle 1+\frac{n}{|X|}$ $\displaystyle\leq$
$\displaystyle 1+\frac{n}{r+3}$ $\displaystyle=$
$\displaystyle\frac{n+k+4}{k+3}.$

Claim 3. $I(G)\leq\frac{3(r+3)+n-1}{r+3}$.

Assume that there are $a$ isolated vertices, $b$ $K_{3}$’s and $c$ triangular-
cactus with at least 5 vertices in the subgraph $H-X$. Let $Y$ be the set of
two vertices of every $K_{3}$. Denote the triangular-cactus with at least 5
vertices in the subgraph $H-X$ by $H_{1},H_{2},\ldots,H_{c}$. Then

$c_{tc}(H-X)=a+b+c,$

Let $I_{i}$ be a maximum independent set of $H_{i}$ for any
$i\in\\{1,2,\ldots,c\\}$.

Claim 3.1. $|I_{i}|\geq\frac{|V(H_{i})|}{3}$ and $|I_{i}|\geq 2$.

$a+b+\left(\sum_{i=1}^{c}|I_{i}|\right)\geq a+b+2c\geq
a+b+c=c_{tc}(H-X)\geq|X|+1,$

We next distinguish four cases below to prove the conclusion.

Case 1. $u,v\in V(H_{i})$ for some $i\in\\{1,2,\ldots,c\\}$ or $u\in V(H_{i})$
and $v\in V(H_{i})$ for some $i,j\in\\{1,2,\ldots,c\\}$.

In this case, we have that $c\geq 1$.

Sub-Case 1.1. Assume that $c=1$. Then we claim $i(G-W-X-Y-V(H_{1})\setminus
I_{1})\geq k+4$. If $|I_{1}|=2$, then $|V(H_{1})|=5$ and there is an $I_{1}$
with $u,v\notin I_{1}$. Thus,

$\displaystyle i(G-W-X-Y-V(H_{1})\setminus I_{1})$ $\displaystyle=$
$\displaystyle i(G-W-e-X-Y-V(H_{1})\setminus I_{1})-2$ $\displaystyle=$
$\displaystyle a+b+2$ $\displaystyle>$ $\displaystyle|X|+1$
$\displaystyle\geq$ $\displaystyle k+4.$

If $|I_{i}|\geq 3$, then

$\displaystyle i(G-W-X-Y-V(H_{1})\setminus I_{1})$ $\displaystyle\geq$
$\displaystyle i(G-W-e-X-Y-V(H_{1})\setminus I_{1})-2$ $\displaystyle=$
$\displaystyle i(H-X-Y-V(H_{1}))-2$ $\displaystyle\geq$ $\displaystyle
a+b+|I_{1}|-2$ $\displaystyle\geq$ $\displaystyle a+b+1$ $\displaystyle=$
$\displaystyle a+b+c$ $\displaystyle\geq$ $\displaystyle|X|+1$
$\displaystyle\geq$ $\displaystyle k+4.$

The conclusion is true.

Thus,

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup Y\cup
V(H_{1})\setminus I_{1})}{i(G-W-X-Y-V(H_{1})\setminus I_{1})}$
$\displaystyle=$
$\displaystyle\frac{n+|X|+2b+(|V(H_{1})|-|I_{1}|)}{a+b+|I_{1}|}$
$\displaystyle\leq$ $\displaystyle\frac{n+|X|+2a+2b+2|I_{1}|}{a+b+|I_{1}|}$
$\displaystyle=$ $\displaystyle 2+\frac{n+|X||}{a+b+|I_{1}|}$
$\displaystyle\leq$ $\displaystyle 2+\frac{n+|X|}{|X|+1}$ $\displaystyle=$
$\displaystyle 3+\frac{n-1}{|X|+1}$ $\displaystyle<$ $\displaystyle
3+\frac{n-1}{k+3}$ $\displaystyle=$ $\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Sub-Case 1.2. If $c\geq 2$, then $2(c-1)\geq c$.

Without loss of generality, we may assume that $i=c$. Then

$\displaystyle i\left(G-W-X-Y-\sum_{i=1}^{c-1}(V(H_{i})\setminus
I_{i})\right)$ $\displaystyle=$ $\displaystyle i\left(G-W-e-
X-Y-\sum_{i=1}^{c-1}(V(H_{i})\setminus I_{i})\right)$ $\displaystyle=$
$\displaystyle i\left(H-X-Y-\sum_{i=1}^{c-1}(V(H_{i})\setminus I_{i})\right)$
$\displaystyle\geq$ $\displaystyle a+b+\left(\sum_{i=1}^{c-1}|I_{i}|\right)$
$\displaystyle\geq$ $\displaystyle a+b+2(c-1)$ $\displaystyle\geq$
$\displaystyle a+b+c$ $\displaystyle\geq$ $\displaystyle|X|+1$
$\displaystyle\geq$ $\displaystyle k+4.$

Thus,

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup
Y\cup\sum_{i=1}^{c-1}(V(H_{i})\setminus I_{i})}{i(G-W-
X-Y-\sum_{i=1}^{c-1}(V(H_{i})\setminus I_{i}))}$ $\displaystyle=$
$\displaystyle\frac{n+|X|+2b+\sum_{i=1}^{c-1}(|V(H_{i})|-|I_{i}|)}{a+b+\sum_{i=1}^{c-1}|I_{i}|}$
$\displaystyle=$
$\displaystyle\frac{n+|X|+2b+\sum_{i=1}^{c-1}|V(H_{i})|-\sum_{i=1}^{c-1}|I_{i}|}{a+b+\sum_{i=1}^{c-1}|I_{i}|}$
$\displaystyle\leq$
$\displaystyle\frac{n+|X|+2a+2b+3\sum_{i=1}^{c-1}|I_{i}|-\sum_{i=1}^{c-1}|I_{i}|}{a+b+\sum_{i=1}^{c-1}|I_{i}|}$
$\displaystyle=$
$\displaystyle\frac{n+|X|+2a+2b+2\sum_{i=1}^{c-1}|I_{i}|}{a+b+\sum_{i=1}^{c-1}|I_{i}|}$
$\displaystyle=$ $\displaystyle 2+\frac{n+|X|}{a+b+\sum_{i=1}^{c-1}|I_{i}|}$
$\displaystyle\leq$ $\displaystyle 2+\frac{n+|X|}{|X|+1}$ $\displaystyle=$
$\displaystyle 3+\frac{n-1}{|X|+1}$ $\displaystyle<$ $\displaystyle
3+\frac{n-1}{k+3}$ $\displaystyle\leq$ $\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Case 2. $u,v\in(aK_{1})$ or $u\in(aK_{1})$ and $v\in(H_{i})$ for some
$i\in\\{1,2,\ldots,c\\}$. In this case, $a\geq 1$ and

$\displaystyle i\left(G-W-X-Y-\\{u\\}-\sum_{i=1}^{c}(V(H_{i})\setminus
I_{i})\right)$ $\displaystyle=$ $\displaystyle i\left(G-W-e-
X-Y-\\{u\\}-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})\right)$ $\displaystyle=$
$\displaystyle i\left(H-X-Y-\\{u\\}-\sum_{i=1}^{c}(V(H_{i})\setminus
I_{i})\right)$ $\displaystyle\geq$ $\displaystyle
a-1+b+\left(\sum_{i=1}^{c}|I_{i}|\right).$

Sub-Case 2.1. If $a=1$, then $c\geq 1$. We have that

$\displaystyle a-1+b+\left(\sum_{i=1}^{c}|I_{i}|\right)$ $\displaystyle\geq$
$\displaystyle a-1+b+2c$ $\displaystyle=$ $\displaystyle a+b+c+c-1$
$\displaystyle\geq$ $\displaystyle a+b+c$ $\displaystyle\geq$
$\displaystyle|X|+1$ $\displaystyle\geq$ $\displaystyle k+4.$

Thus,

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup
Y\cup\\{u\\}\cup\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})}{i(G-W-
X-Y-\\{u\\}-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i}))}$ $\displaystyle=$
$\displaystyle\frac{n+|X|+2b+1+\sum_{i=1}^{c}(|V(H_{i})|-|I_{i}|)}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle\leq$
$\displaystyle\frac{n+|X|+1+2(a-1)+2b+2\sum_{i=1}^{c}|I_{i}|}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle=$ $\displaystyle 2+\frac{n+|X|+1}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle\leq$ $\displaystyle 2+\frac{n+|X|+1}{|X|+1}$ $\displaystyle=$
$\displaystyle 3+\frac{n}{|X|+1}$ $\displaystyle<$
$\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Sub-Case 2.2. If $a\geq 2$, then $2(a-1)-2\geq 0$ and

$\displaystyle a-1+b+\left(\sum_{i=1}^{c}|I_{i}|\right)$ $\displaystyle\geq$
$\displaystyle a-1+b+2c$ $\displaystyle\geq$ $\displaystyle a+b+c-1$
$\displaystyle\geq$ $\displaystyle|X|$ $\displaystyle\geq$ $\displaystyle
k+3.$

Thus, similar to Sub-Case 2.1, we have that

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup
Y\cup\\{u\\}\cup\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})}{i(G-W-
X-Y-\\{u\\}-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i}))}$ $\displaystyle\leq$
$\displaystyle\frac{n+|X|+2b+1+2\sum_{i=1}^{c}|I_{i}|}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle=$
$\displaystyle\frac{n+|X|+2(a-1)-2+2b+1+2\sum_{i=1}^{c}|I_{i}|}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle=$ $\displaystyle 2+\frac{n+|X|-1}{a-1+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle\leq$ $\displaystyle 2+\frac{n+|X|-1}{|X|}$ $\displaystyle=$
$\displaystyle 3+\frac{n-1}{|X|}$ $\displaystyle\leq$ $\displaystyle
3+\frac{n-1}{k+3}$ $\displaystyle=$ $\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Case 3. $u,v\in V(Q)$, or $u\in(aK_{3})$ and $v\in(bK_{1})$, or $u\in(aK_{3})$
and $v\in(H_{i})$ for some $i\in\\{1,2,\ldots,c\\}$, or $u\in(aK_{3})$ and
$v\in(Q)$. Let $u\in Y$ if $u\in(aK_{3})$ and $u,v\in Y$ if $u,v\in(aK_{3})$.

$\displaystyle i\left(G-W-X-Y-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})\right)$
$\displaystyle=$ $\displaystyle i\left(G-W-e-
X-Y-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})\right)$ $\displaystyle=$
$\displaystyle i\left(H-X-Y-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})\right)$
$\displaystyle\geq$ $\displaystyle a+b+\left(\sum_{i=1}^{c}|I_{i}|\right)$
$\displaystyle\geq$ $\displaystyle|X|+1$ $\displaystyle\geq$ $\displaystyle
k+4.$

Thus, similar to Sub-Case 1.2, we have that

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup
Y\cup\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})}{i(G-W-
X-Y-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i}))}$ $\displaystyle\leq$
$\displaystyle 2+\frac{n+|X|}{|X|+1}$ $\displaystyle=$ $\displaystyle
3+\frac{n-1}{|X|+1}$ $\displaystyle\leq$ $\displaystyle 3+\frac{n-1}{k+4}$
$\displaystyle<$ $\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Case 4. $u\in(aK_{1})$ and $v\in(Q_{j})$ for some $j\in\\{1,2,\ldots,d\\}$. In
this case, $a\geq 1$

$\displaystyle i\left(G-W-X-Y-\\{v\\}-\sum_{i=1}^{c}(V(H_{i})\setminus
I_{i})\right)$ $\displaystyle=$ $\displaystyle i\left(G-W-e-
X-Y-\\{v\\}-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})\right)$ $\displaystyle=$
$\displaystyle i\left(H-X-Y-\\{v\\}-\sum_{i=1}^{c}(V(H_{i})\setminus
I_{i})\right)$ $\displaystyle\geq$ $\displaystyle
a+b+\left(\sum_{i=1}^{c}|I_{i}|\right)$ $\displaystyle\geq$
$\displaystyle|X|+1$ $\displaystyle\geq$ $\displaystyle k+4.$

Similar to Sub-Case 2.1, we have that

$\displaystyle I(G)$ $\displaystyle\leq$ $\displaystyle\frac{W\cup X\cup
Y\cup\\{v\\}\cup\sum_{i=1}^{c}(V(H_{i})\setminus I_{i})}{i(G-W-
X-Y-\\{v\\}-\sum_{i=1}^{c}(V(H_{i})\setminus I_{i}))}$ $\displaystyle=$
$\displaystyle\frac{n+|X|+2b+1+\sum_{i=1}^{c}(|V(H_{i})|-|I_{i}|)}{a+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle\leq$
$\displaystyle\frac{n+|X|+2a-2+2b+1+2\sum_{i=1}^{c}|I_{i}|}{a+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle=$ $\displaystyle 2+\frac{n+|X|-1}{a+b+\sum_{i=1}^{c}|I_{i}|}$
$\displaystyle\leq$ $\displaystyle 2+\frac{n+|X|-1}{|X|+1}$ $\displaystyle=$
$\displaystyle 3+\frac{n-2}{|X|+1}$ $\displaystyle<$ $\displaystyle
3+\frac{n-1}{k+3}$ $\displaystyle=$ $\displaystyle\frac{3(k+3)+n-1}{k+3}.$

Thus, the conclusion holds.

######  Remark 3.2.

If $G$ is $(n+k+3)$-connected, then $t(G)>\frac{n+k+4}{k+3}$ in Theorem 1.2 is
best possible.

For two nonnegative integers $n$ and $k$ with $n\geq k+1$, let
$G=K_{n+k+3}+((k+2)K_{1}\cup K_{2})$ again. It is easy to see that $G$ is
$(n+k+3)$-connected and $t(G)=\frac{n+k+4}{k+3}$. Then $G$ is not a
$\\{K_{2},C_{n}\\}$-factor critical avoidable graph by Remark 2.2.

######  Remark 3.3.

If $G$ is $(n+k+3)$-connected, then $I(G)>\frac{3(k+3)+n-1}{k+3}$ in Theorem
1.2 is best possible.

For two nonnegative integers $n$ and $k$ with $n\geq k+1$, let
$G=K_{n+k+3}+((k+2)K_{3}\cup K_{2})$. It is easy to see that $G$ is
$(n+k+3)$-connected and $I(G)=\frac{3(k+3)+n-1}{k+3}$. Assume that $W\subset
V(K_{n+k+3})\subset V(G)$ and $e=E(K_{2})$. Then
$G-W-e=K_{k+3}+((k+2)K_{3}\cup 2K_{1})$. Let $X=V(K_{k+3})$ in the subgraph
$G-W-e$. Then $c_{tc}(G-W-e-X)=k+4>k+3=|X|$. This implies that $G$ is not a
$\\{K_{2},C_{2i+1}|i\geq 2\\}$-factor critical avoidable graph by Theorem 3.1.

######  Remark 3.4.

The condition on $(n+k+3)$-connected of Theorem 1.2 is best possible.

For two nonnegative integers $n$ and $k$ with $n\geq k+1$, let
$G=K_{n+k+2}+((k+1)K_{1}\cup K_{2})$. Then $G$ is $(n+k+2)$-connected but not
a $\\{K_{2},C_{n}\\}$-factor critical avoidable graph by Remark 2.3. This
implies that $G$ is not a $\\{K_{2},C_{2i+1}|i\geq 2\\}$-factor critical
avoidable graph, either.

## Acknowledgements

This work was supported by the National Natural Science Foundation of China
(No. 12301455), the Natural Science Foundation of Shandong Province (No.
ZR2023QA080).

## References

## References

  * [1] V. Chvátal, Tough graphs and Hamiltonian circuits, _Discrete Math._ 5 (1973) 215-228.
  * [2] G. Cornuejols, W.R. Pulleyblank, Perfect triangle-free $2$-matchings, Combinatorial optimization, II (Proc. Conf. Univ. East Anglia, Norwich,1979), _Math. Program. Stud._ 13 (1980) 1-7.
  * [3] E. Scheinerman, D. Ullman, _Fractional Graph Theory: A Rational Approach to the Theory of Graphs_ , John Wiley, New York, 1997\.
  * [4] J. Yang, Y. Ma, G. Liu, Fractional $(g,f)$-factors in graphs, _Appl. Math. J. Chinese Univ. Ser. A_ 16 (2001) 385-390.
  * [5] S. Zhou, Q. Bian, Q. Pan, Path factors in subgraphs, _Discrete Appl. Math._ 319 (2022) 183–191.
  * [6] S. Zhou, J. Wu, Q. Bian, On path-factor critical deleted (or covered) graphs, _Aequationes Mathematicae_ 96 (2022) 795–802.
  * [7] S. Zhou, H. Liu, Some existence theorems on path-factor critical avoidable graphs, _RAIRO-Oper. Res._ 58 (2024) 2015–2027.