Isolated toughness and fractional (a,b,n)-critical graphs

Abstract

A graph G is a fractional $(a,b,n)$-critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional $[a,b]$-factor. In this paper, we determine the exact tight isolated toughness bound for fractional $(a,b,n)$-critical graphs. To be specific, a graph G is fractional $(a,b,n)$-critical if $\delta (G)\ge a+n$ and $I(G)>a-1+\frac{n+1}{n_{a,b}}$, where $n_{a,b}\ge 2$ is an integer satisfies $(n_{a,b}-1)a\le b\le n_{a,b}a-1$. Furthermore, the sharpness of bounds is showcased by counterexamples. Our contribution improves a result from [W. Gao, W. Wang, and Y. Chen, Tight isolated toughness bound for fractional $(k,n)$-critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional $(k,n)$-critical graphs.

Keywords:

• Graph
• isolated toughness
• fractional $[a,b]$-factor
• fractional $(a,b,n)$-critical graph

AMS:

• 05C70

1. Introduction

The graphs we discuss in this paper are simple and finite. Let G be a graph with vertex set $V(G)$ and edge set $E(G)$. We denote $d_G(v)$ and $N_G(v)$ (simply by $d(v)$ and $N(v)$) as the degree and the neighbourhood of vertex v in G respectively, and $\delta (G)$ is the minimum degree of G which took the smallest value of $d_G(v)$ among all vertices. Let $G[S]$ be the subgraph of G induced by $S\subseteq V(G)$. Denote $i(G)$ as the number of isolated vertices in G. The operator $\vee$ in $G_1\vee G_2$ means adding edges for all pairs of vertices between $G_1$ and $G_2$. The notations and terminologies used but undefined in this paper can be referred to Bondy and Murty (2008).

Let a, b, k be positive integers with $1\le a\le b$, and $h:E(G)\to [0,1]$ be an indicator function defined on the edge set. A fractional $[a,b]$-factor is a spanning subgraph consisting of edge set $E_h=\{e\in E(G)|h(e)>0\}$ such that (1) $a\le d_G^h(v)=\sum _{v^{\prime }\in N(v)}h(v{v}^{\prime })\le b$(1) for any $v\in V(G)$. A graph G admits a fractional $[a,b]$-factor means there is an indictor function h meeting (1(1) $a\le d_G^h(v)=\sum _{v^{\prime }\in N(v)}h(v{v}^{\prime })\le b$(1) ). For $n\in \mathbb{N}$, G is a fractional $(a,b,n)$-critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional $[a,b]$-factor. In particular, if a = b = k, then fractional $[a,b]$-factor and fractional $(a,b,n)$-critical graph are degenerated to fractional k-factor and fractional $(k,n)$-critical graph, respectively, which are the original versions of fractional factor and fractional critical graph.

As a salient graph parameter, isolated toughness is introduced by Yang et al. (2001) which is stated as $I(G)=min\{\frac{|S|}{i(G-S)}|S\subset V(G),i(G-S)\ge 2\}$ if G is not a complete graph, and $I(G)=+\mathrm{\infty }$ if G is a complete graph.

In recent two decades, with the advancement of graph theory technology and spread networks applicability, fractional factor has developed into a prominent research field in both graph theory and computer networks, and has achieved crucial theoretical results. Ma and Liu (2006) contended that a graph G admits a fractional k-factor if $\delta (G)\ge k$ and $I(G)\ge k$. Gao and Wang (2017) determined that G is a fractional $(a,b,n)$-critical graph if $I(G)\ge \frac{ab-2\mathrm{\Delta }}{a}+n$, where $2\le a\le b$ and $\mathrm{\Delta }=b-a$. Gao et al. (2022) proved the tight isolated toughness bound for a graph G to be fractional $(k,n)$-critical, i.e. G is a fractional $(k,n)$-critical graph if $\delta (G)\ge k+n$ and $I(G)>k+\frac{n-1}{2}$, where $k\ge 2$. Zhou (2021) and Zhou, Liu, Xu (2022) studied the graph parameter conditions of fractional critical covered graph which inquires fractional factors with given edges after removing fixed number of vertices. More results on this topic and other extensions can be referred to Chang et al. (2022), Chen et al. (2022), Zhou, Wu, Bian (2022), Zhou, Wu, Liu (2022) and Zhou, Wu, Xu (2022).

Although there are fruitful advances in the correlation of isolated toughness and the existence of fractional factor, the study of generalisation properties of fractional factors has been largely limited to the special setting, especially the tight $I(G)$ bounds are open problems in most fractional critical graph settings. Motivated by the aforementioned facts, in this paper, we determine the sharp isolated toughness bound for a graph to be fractional $(a,b,n)$-critical, and our main conclusion is stated as follows which extends the previous result in Gao et al. (2022).

Theorem 1.1

Let G be a graph, and a, b, n be positive integers with $2\le a\le b$ and $(n_{a,b}-1)a\le b\le n_{a,b}a-1$, where $n_{a,b}\ge 2$ is an integer. If $\delta (G)\ge a+n$ and $I(G)>a-1+\frac{n+1}{n_{a,b}}$, then G is a fractional $(a,b,n)$-critical graph.

To be obvious, $\delta (G)\ge a+n$ is tight for a graph G to be fractional $(a,b,n)$-critical in terms of the definition of fractional $[a,b]$-factor. The sharpness of $I(G)$ in Theorem 1.1 is showcased in the following instance.

Consider $G=K_{n+1}\vee (n_{a,b}{K}_a)$ where a, b, n are positive integers with $b\ge a\ge 2$, and $n_{a,b}\ge 2$ is an integer which is determined by the correlation $b=(n_{a,b}-1)a+c$ with $c\in \{0,1,\dots ,a-1\}$. We directly get $I(G)=\frac{(n+1)+n_{a,b}(a-1)}{n_{a,b}}=a-1+\frac{n+1}{n_{a,b}}.$ On the other hand, set $S=V(K_{n+1})$ and $T=V(n_{a,b}{K}_a)$, we yield $b|S|-a|T|+\sum _{x\in T}{d}_{G-S}(x)=b(n+1)-n_{a,b}a=bn+b-n_{a,b}a<bn.$ Thus, G is not a fractional $(a,b,n)$-critical graph by means of Lemma 2.2.

By setting a = b = k in Theorem 1.1, $n_{a,b}=2$ and thus the following corollary is derived for fractional $(k,n)$-critical graphs.

Corollary 1.1

Gao et al., 2022

Let G be a graph, $n\ge 1$ and $k\ge 2$ be integers. If $\delta (G)\ge k+n$ and $I(G)>k+\frac{n-1}{2}$, then G is a fractional $(k,n)$-critical graph.

The remainder of the paper is arranged as follows. Several useful lemmas and remarks are presented in the next section. Then, the detailed proof of Theorem 1.1 is presented. Finally, we discuss some interesting topics for future studies.

2. Preliminary

The necessary and sufficient condition of fractional $(a,b,n)$-critical graph is imperative to prove our main theorem which is determined by Liu (2010).

Lemma 2.1

Liu, 2010

Let a, b and n be positive integers such that $a\le b$. Then a graph G is fractional $(a,b,n)$-critical if and only if $b|S|-a|T|+\sum _{x\in T}{d}_{G-S}(x)\ge bn$ holds for any $S\subseteq V(G)$ with $|S|\ge n$, where $T=\{x\in V(G)-S|d_{G-S}(x)\le a\}$.

It is noteworthy that for a given subset S of $V(G)$, T is determined by S which can be rewritten by $T=\{x\in V(G)-S|d_{G-S}(x)\le a-1\}$. We emphasise that Lemma 2.1 has its equal expression which is manifested below.

Lemma 2.2

Liu, 2010

Let a, b and n be positive integers such that $a\le b$. Then a graph G is fractional $(a,b,n)$-critical if and only if $b|S|-a|T|+\sum _{x\in T}{d}_{G-S}(x)\ge bn$ holds for any disjoint subsets $S,T\subseteq V(G)$ with $|S|\ge n$.

The following lemma is obtained by slightly revising the Lemma 2.2 in Liu and Zhang (2008) in view of its proving process which presents the characteristic of independent sets and covering sets in specific settings.

Lemma 2.3

Liu & Zhang, 2008

Let G be a graph and let $H=G[T]$ such that $d_G(x)=k-1$ for every $x\in V(H)$ and no component of H is isomorphic to $K_k$ where $T\subseteq V(G)$ and $k\ge 2$ is an integer. Then there exists an independent set I and the covering set $C=V(H)-I$ of H satisfying $|V(H)|\le \sum _{i=1}^k(k-i+1)|I^{(i)}|-\frac{|I^{(1)}|}{2}$ and $|C|\le \sum _{i=1}^k(k-i)|I^{(i)}|-\frac{|I^{(1)}|}{2}$ where $I^{(i)}=\{x\in I,d_H(x)=k-i\}$ for $1\le i\le k$ and $\sum _{i=1}^k|I^{(i)}|=|I|$.

The crux of our proofing strategy is to get the integer upper bound of $|S|$ (or $|U|$ instead), with the aim to eliminate the decimal part of $|S|$ and obtain the desired conclusion. Another crucial trick in the proof process is to get the lower bound of the denominator of isolated toughness ($|T_0|+l+|I_1|+|I_2|$, some terms may become zero in special cases). It is observed from the derivation in the next section that the lower bound of $|T_0|+l+|I_1|+|I_2|$ depends on $n_{a,b}$, i.e. the correlation between a and b determines lower bound of denominator to maximise the $I(G)$, and then we infer the contradiction.

3. Proof of theorem thm1.1

If G is complete, the result is directly yielded by means of $\delta (G)\ge a+n$. In what follows, we always assume that G is not complete. Suppose that G satisfies the conditions of Theorem 1.1, but is not a fractional $(a,b,n)$-critical graph. By Lemma 2.2, there exist disjoint subsets S and T of $V(G)$ with $|S|\ge n$ satisfying (2) $b|S|-a|T|+\sum _{x\in T}{d}_{G-S}(x)=b|S|+\sum _{x\in T}(d_{G-S}(x)-a)\le bn-1.$(2) We choose S and T such that $|T|$ is minimum. Thus, $T\ne \mathrm{\varnothing }$, and $d_{G-S}(x)\le a-1$ for any $x\in T$. Furthermore, due to $\delta (G)\ge a+n$, we obtain the following observation.

Observation 3.1

$|S|\ge n+1$.

Let l be the number of the components of $H^{\prime }=G[T]$ which are isomorphic to $K_a$ and let $T_0=\{x\in V(H^{\prime })|d_{G-S}(x)=0\}$. Let H be the subgraph inferred from $H^{\prime }-T_0$ by deleting those l components isomorphic to $K_a$. Let $S^{\prime }$ be a set of vertices that contains exactly a−1 vertices in each component of $K_a$ in $H^{\prime }$.

If $|V(H)|=0$, then from (2(2) $b|S|-a|T|+\sum _{x\in T}{d}_{G-S}(x)=b|S|+\sum _{x\in T}(d_{G-S}(x)-a)\le bn-1.$(2) ) and Observation 3.1, we yield $n+1\le |S|\le \frac{a(|T_0|+l)-1}{b}+n$, i.e. $b\le a(|T_0|+l)-1$ which implies $|T_0|+l\ge 2$ and $|T_0|+l\ge \frac{b+1}{a}\ge \frac{(n_{a,b}-1)a+1}{a}$. Thus, $|T_0|+l\ge n_{a,b}$. In light of the definition of isolated toughness, we deduce $i(G-S\cup S^{\prime })=|T_0|+l\ge 2$ and $\begin{array}{rl}I(G)& \le \frac{|S\cup S^{\prime }|}{i(G-S-S^{\prime })}\le \frac{\lfloor \frac{a(|T_0|+l)-1}{b}+n+l(a-1)\rfloor }{|T_0|+l}\\ & \le \frac{\lfloor (a-1+\frac{a}{b})(|T_0|+l)+n-\frac{1}{b}\rfloor }{|T_0|+l}\\ & =a-1+\frac{n+\lfloor \frac{a(|T_0|+l)-1}{b}\rfloor }{|T_0|+l}.\end{array}$ Let $a(|T_0|+l)-1=m_{1}b+c_1$, where $m_1\in \mathbb{N}\cup \{0\}$ and $c_1\in \{0,\dots ,b-1\}$. Then, by $\frac{1}{b}\le \frac{c_1+1}{b}\le 1$ and $n\ge 1$, we infer $\begin{array}{rl}a-1+max\left\{\frac{n+\lfloor \frac{a(|T_0|+l)-1}{b}\rfloor }{|T_0|+l}\right\}& =a-1+max\left\{\frac{n+\frac{a(|T_0|+l)-1}{b}-\frac{c_1}{b}}{|T_0|+l}\right\}\\ & =a-1+\frac{a}{b}+max\left\{\frac{n-\frac{c_1+1}{b}}{|T_0|+l}\right\}\\ & =a-1+\frac{a}{b}+\frac{n-\frac{c_1+1}{b}}{n_{a,b}},\end{array}$ which implies that $a-1+\frac{n+\lfloor \frac{a(|T_0|+l)-1}{b}\rfloor }{|T_0|+l}$ arrives at the maximum value when $|T_0|+l$ reaches its lower bound $n_{a,b}$. Hence, $\begin{array}{rl}I(G)& \le a-1+\frac{n+\lfloor \frac{a{n}_{a,b}-1}{b}\rfloor }{n_{a,b}}\\ & \le a-1+\frac{n+\lfloor \frac{a{n}_{a,b}-1}{(n_{a,b}-1)a}\rfloor }{n_{a,b}}\\ & =a-1+\frac{n+1}{n_{a,b}},\end{array}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}$.

Hence, we have $|V(H)|>0$. Let $H=H_1\cup H_2$ where $H_1$ is the union of components of H which satisfies that $d_{G-S}(v)=a-1$ for each vertex $v\in V(H_1)$ and $H_2=H-H_1$. By means of Lemma 2.3, $H_1$ has a maximum independent set $I_1$ and the covering set $C_1=V(H_1)-I_1$ such that (3) $|V(H_1)|\le \sum _{i=1}^a(a-i+1)|I^{(i)}|-\frac{|I^{(1)}|}{2}\le (a-\frac{1}{2})|I_1|,$(3) and (4) $|C_1|\le \sum _{i=1}^a(a-i)|I^{(i)}|-\frac{|I^{(1)}|}{2},$(4) where $I^{(i)}=\{v\in I_1,d_{H_1}(v)=a-i\}$ for $1\le i\le a$ and $\sum _{i=1}^a|I^{(i)}|=|I_1|$. Using the definition of H and $H_2$, we verify that each component of $H_2$ has a vertex of degree at most a−2 in G−S. Clearly, if $H_2\ne \mathrm{\varnothing }$, then $a\ge 3$, and $I_2$ can be selected by Algorithm 1 (Gao et al., 2022):

Moreover, we have the following observation due to $\delta (G)\ge a+n$ and at least one vertex in $I_2$ has degree at most a−2 in G−S.

Observation 3.2

If $H_2\ne \mathrm{\varnothing }$, then $|S|\ge n+2$.

Set $W=V(G)-S-T$ and $U=S\cup S^{\prime }\cup C_1\cup (N_G(I_1)\cap W))\cup N_{G-S}(I_2)=S\cup S^{\prime }\cup N_{G-S}(I_1)\cup N_{G-S}(I_2)$. The subsequent discussion is divided into two situations.

Case 1. $|T_0|+l\ge 1$.

The following two claims confirm that $H_1$ or $H_2$ can not exist independently.

Claim 3.1

If $|T_0|+l\ge 1$, then $|I_2|\ne 0$.

Proof.

Suppose $|I_2|=0$. Then $|I_1|\ne 0$ by $|V(H)|>0$.

We partition $I_1$ into two subsets.

$I_{11}$: $v\in I_{11}$ if there exists $v^{\prime }\in I_1\setminus \{v\}$ such that $N_{G-S}(v)\cap N_{G-S}(v^{\prime })\ne \mathrm{\varnothing }$;

$I_{12}$: $v\in I_{12}$ if there is no intersection between $N_{G-S}(v)$ and $N_{G-S}(I_1\setminus \{v\})$.

We yield $b|S|\le |V(H_1)|+a|T_0|+la+bn-1\le (a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|+a(|T_0|+l)+bn-1$ and $\begin{array}{rl}|S|& \le (\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|-\frac{1}{b}+\frac{a(|T_0|+l)}{b}+n\\ & <\frac{a(|T_0|+l+|I_1|)}{b}+n.\end{array}$ In view of Observation 3.1, we deduce $|T_0|+l+|I_1|>\frac{b}{a}$ which implies $|T_0|+l+|I_1|\ge n_{a,b}$.

Moreover, $\begin{array}{rl}|S\cup S^{\prime }\cup N_{G-S}(I_1)|& \le (\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|-\frac{1}{b}+\frac{a(|T_0|+l)}{b}+n\\ & +l(a-1)+(a-1-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|\\ & =(a-1+\frac{a}{b}-\frac{b+1}{2b})|I_{11}|+(a-1+\frac{a}{b}-\frac{1}{b})|I_{12}|+\frac{a}{b}|T_0|\\ & +(a-1+\frac{a}{b})l+n-\frac{1}{b}\\ & \le (a-1+\frac{a}{b})(|T_0|+l)+(a-1+\frac{a}{b}-\frac{1}{b})|I_1|+n-\frac{1}{b}\\ & \le (a-1+\frac{a}{b})(|I_1|+|T_0|+l)+n-\frac{2}{b}\end{array}$ and thus $\begin{array}{rl}I(G)& \le \frac{|S\cup S^{\prime }\cup N_{G-S}(I_1)|}{i(G-S\cup S^{\prime }\cup N_{G-S}(I_1))}\\ & \le \frac{\lfloor (a-1+\frac{a}{b})(|I_1|+l+|T_0|)+n-\frac{2}{b}\rfloor }{|I_1|+l+|T_0|}\\ & =a-1+\frac{\lfloor \frac{a(|I_1|+l+|T_0|)-2}{b}\rfloor +n}{|I_1|+l+|T_0|}.\end{array}$ Let $a(|I_1|+l+|T_0|)-2=m_{2}b+c_2$, where $m_2\in \mathbb{N}\cup \{0\}$ and $c_2\in \{0,\dots ,b-1\}$. Then, we obtain $\begin{array}{rl}a-1+max\left\{\frac{\lfloor \frac{a(|I_1|+l+|T_0|)-2}{b}\rfloor +n}{|I_1|+l+|T_0|}\right\}& =a-1+max\left\{\frac{\frac{a(|I_1|+l+|T_0|)-2-c_2}{b}+n}{|I_1|+l+|T_0|}\right\}\\ & =a-1+\frac{a}{b}+max\left\{\frac{n-\frac{2+c_2}{b}}{|I_1|+l+|T_0|}\right\}.\end{array}$ If n = 1 and $c_2=b-1$, then $\frac{n-\frac{2+c_2}{b}}{|I_1|+l+|T_0|}$ is negative, thus $I(G)<a-1+\frac{a}{b}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $\frac{n-\frac{2+c_2}{b}}{|I_1|+l+|T_0|}$ is a non-negative term and $\frac{n-\frac{2+c_2}{b}}{|I_1|+l+|T_0|}$ reaches the maximum value when $|T_0|+l+|I_1|$ reaches its lower bound $n_{a,b}$. Therefore, $I(G)\le a-1+\frac{\lfloor \frac{a{n}_{a,b}-2}{b}\rfloor +n}{n_{a,b}}\le a-1+\frac{\lfloor \frac{a{n}_{a,b}-2}{(n_{a,b}-1)a}\rfloor +n}{n_{a,b}}=a-1+\frac{n+1}{n_{a,b}},$ which contradicts to the hypothesis of $I(G)$.

Claim 3.2

If $|T_0|+l\ge 1$, then $|I_1|\ne 0$.

Proof.

Suppose $|I_1|=0$. We yield $|I_2|\ne 0$ by $|V(H)|>0$, and hence $a\ge 3$.

Let $v_1,v_2,\dots ,v_{|I_2|}$ be vertices in $I_2$ such that $d_{G-S}(v_1)\le a-2$ and $d_{G-S}(v_1)\le d_{G-S}(v_2)\le \cdots \le d_{G-S}(v_{|I_2|})$. Then $|V(T)|=|V(H_2)|+|T_0|+al$, $\begin{array}{rl}b|S|& \le a|T|-d_{G-S}(T)+bn-1\\ & \le a|T_0|+al+\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))+bn-1\end{array}$ and $|S|\le \frac{a(|T_0|+l)}{b}+\frac{\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))}{b}+n-\frac{1}{b}.$ We acquire $i(G-U)\ge 2$ where $U=S\cup S^{\prime }\cup N_{G-S}(I_2)$ and $\begin{array}{rl}|U|& \le |S|+|S^{\prime }|+|N_{G-S}(I_2)|\\ & \le \frac{a(|T_0|+l)}{b}+\frac{\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))}{b}+n-\frac{1}{b}+l(a-1)+\sum _{i=1}^{|I_2|}{d}_{G-S}(v_i)\\ & =\frac{a|T_0|}{b}+l(a-1+\frac{a}{b})+\sum _{i=1}^{|I_2|}(-\frac{d_{G-S}^2(v_i)}{b}+\frac{a+b-1}{b}{d}_{G-S}(v_i)+\frac{a}{b})+n-\frac{1}{b}\\ & \le \frac{a|T_0|}{b}+l(a-1+\frac{a}{b})+(-\frac{(a-2{)}^2}{b}+\frac{a+b-1}{b}(a-2)+\frac{a}{b})\\ & +(|I_2|-1)(-\frac{(a-1{)}^2}{b}+\frac{a+b-1}{b}(a-1)+\frac{a}{b})+n-\frac{1}{b}\\ & =\frac{a|T_0|}{b}+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}.\end{array}$ It is clear to see that to acquire the extremum isolated toughness, we maximise $|U|$ with the given number of $|I_2|$, and thus only one vertex in $I_2$ has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of $|T_0|+l+|I_2|$, it is imperative to re-compute the upper bound of $|S|$ as follows: $\begin{array}{rl}|S|& \le \frac{a(|T_0|+l)}{b}+\frac{(|I_2|-1)(a-1+1)(a-(a-1))+(a-2+1)(a-(a-2))}{b}+n-\frac{1}{b}\\ & =\frac{a(|T_0|+l+|I_2|)+a-3}{b}+n.\end{array}$ Using Observation 3.2, we infer $2+n\le |S|\le \frac{a(|T_0|+l+|I_2|)+a-3}{b}+n,$ which implies $|T_0|+l+|I_2|\ge \frac{2b-a+3}{a}\ge \frac{2(n_{a,b}-1)a-a+3}{a}=2n_{a,b}-3+\frac{3}{a}$, and hence $|T_0|+l+|I_2|\ge 2n_{a,b}-2$.

In terms of the definition of isolated toughness, we verify $\begin{array}{rl}I(G)& \le \frac{|U|}{i(G-U)}\le \frac{\lfloor \frac{a|T_0|}{b}+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}\rfloor }{|I_2|+|T_0|+l}\\ & \le \frac{\lfloor (a-1+\frac{a}{b})(|T_0|+l+|I_2|)+n-1+\frac{a-3}{b}\rfloor }{|I_2|+|T_0|+l}\\ & =a-1+\frac{n-1+\lfloor \frac{a(|T_0|+l+|I_2|)+a-3}{b}\rfloor }{|I_2|+|T_0|+l}.\end{array}$ Let $a(|I_2|+l+|T_0|)+a-3=m_{3}b+c_3$, where $m_3\in \mathbb{N}\cup \{0\}$ and $c_3\in \{0,\dots ,b-1\}$. Then, we infer $\begin{array}{rl}max\left\{\frac{n-1+\lfloor \frac{a(|T_0|+l+|I_2|)+a-3}{b}\rfloor }{|I_2|+|T_0|+l}\right\}& =max\left\{\frac{n-1+\frac{a(|T_0|+l+|I_2|)+a-3-c_3}{b}}{|I_2|+|T_0|+l}\right\}\\ & =\frac{a}{b}+max\left\{\frac{n-1+\frac{a-3-c_3}{b}}{|I_2|+|T_0|+l}\right\}.\end{array}$ If $n-1+\frac{a-3-c_3}{b}$ is negative, then n = 1 and $I(G)<a-1+\frac{a}{b}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $n-1+\frac{a-3-c_3}{b}$ is non-negative and $\frac{n-1+\lfloor \frac{a(|T_0|+l+|I_2|)+a-3}{b}\rfloor }{|I_2|+|T_0|+l}$ arrives at the maximum value when $|I_2|+|T_0|+l$ reaches the lower bound $2n_{a,b}-2$. We deduce $\begin{array}{rl}I(G)& \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-3}{b}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-3}{(n_{a,b}-1)a}\rfloor }{2n_{a,b}-2}\\ & =a-1+\frac{n+1}{2n_{a,b}-2},\end{array}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}$ and $n_{a,b}\ge 2$.

From Claim 3.1 and Claim 3.2, we check $|I_1|>0$, $|I_2|>0$ and $a\ge 3$.

Denote $v_1,v_2,\dots ,v_{|I_2|}$ as vertices in $I_2$ as defined in Claim 3.2. Then $|V(T)|=|V(H_1)|+|V(H_2)|+|T_0|+al$, $\begin{array}{rl}b|S|& \le a|T|-d_{G-S}(T)+bn-1\\ & \le a(|T_0|+l)+(a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|\\ & +\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))+bn-1\end{array}$ and $\begin{array}{rl}|S|& \le \frac{\begin{array}{c}a(|T_0|+l)+(a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|\\ +\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))+bn-1\end{array}}{b}\\ & =\frac{a}{b}(|T_0|+l)+(\frac{a}{b}-\frac{1}{2b})|I_{11}|\\ & +\frac{a-1}{b}|I_{12}|+\frac{\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))}{b}+n-\frac{1}{b}.\end{array}$ We acquire $i(G-U)\ge 3$ where $U=S\cup S^{\prime }\cup C_1\cup (N_G(I_1)\cap W)\cup N_{G-S}(I_2)$ and $\begin{array}{rl}|U|& \le |S|+|S^{\prime }|+|C_1|+|N_G(I_1)\cap W|+|N_{G-S}(I_2)|\\ & \le \frac{a}{b}(|T_0|+l)+(\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|+\frac{\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))}{b}\\ & +n-\frac{1}{b}+l(a-1)+(a-\frac{1}{2}-1)|I_{11}|+(a-1)|I_{12}|+\sum _{i=1}^{|I_2|}{d}_{G-S}(v_i)\\ & \le \frac{a}{b}|T_0|+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b}-\frac{1}{b})|I_1|+(a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}\\ & \le (|T_0|+l)(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_1|+(a-1+\frac{a}{b})|I_2|+n-1+\frac{a-4}{b}.\end{array}$ Similar to the discussion in Claim 3.2, to maximise $|U|$, only one vertex in $I_2$ has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of $|T_0|+l+|I_1|+|I_2|$, it is necessary to re-calculate the upper bound of $|S|$: $\begin{array}{rl}|S|& \le \frac{a(|T_0|+l)}{b}+(\frac{a}{b}-\frac{1}{2b})|I_1|\\ & +\frac{(|I_2|-1)(a-1+1)(a-(a-1))+(a-2+1)(a-(a-2))}{b}+n-\frac{1}{b}\\ & <\frac{a(|T_0|+l+|I_1|+|I_2|)+a-3}{b}+n.\end{array}$ By means of Observation 3.2, we yield $2+n\le |S|<\frac{a(|T_0|+l+|I_1|+|I_2|)+a-3}{b}+n,$ which implies $|T_0|+l+|I_1|+|I_2|>\frac{2b-a+3}{a}\ge \frac{2(n_{a,b}-1)a-a+3}{a}=2n_{a,b}-3+\frac{3}{a}$, and hence $|T_0|+l+|I_1|+|I_2|\ge 2n_{a,b}-2$.

Using the definition of $I(G)$, we obtain $\begin{array}{rl}I(G)& \le \frac{|U|}{i(G-U)}\le \frac{\lfloor (a-1+\frac{a}{b})(|T_0|+l+|I_1|+|I_2|)+n-1+\frac{a-4}{b}\rfloor }{|I_1|+|I_2|+|T_0|+l}\\ & =a-1+\frac{n-1+\lfloor \frac{a(|I_1|+|I_2|+|T_0|+l)+a-4}{b}\rfloor }{|I_1|+|I_2|+|T_0|+l}.\end{array}$ Let $a(|I_1|+|I_2|+|T_0|+l)+a-4=m_{4}b+c_4$, where $m_4\in \mathbb{N}\cup \{0\}$ and $c_4\in \{0,\dots ,b-1\}$. Then, $\begin{array}{rl}max\left\{\frac{n-1+\lfloor \frac{a(|I_1|+|I_2|+|T_0|+l)+a-4}{b}\rfloor }{|I_1|+|I_2|+|T_0|+l}\right\}& =max\left\{\frac{n-1+\frac{a(|I_1|+|I_2|+|T_0|+l)+a-4-c_4}{b}}{|I_1|+|I_2|+|T_0|+l}\right\}\\ & =\frac{a}{b}+max\left\{\frac{n-1+\frac{a-4-c_4}{b}}{|I_1|+|I_2|+|T_0|+l}\right\}.\end{array}$ If $n-1+\frac{a-4-c_4}{b}$ is negative, we get n = 1 and $I(G)<a-1+\frac{a}{b}$, which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $n-1+\frac{a-4-c_4}{b}$ is non-negative and $\frac{n-1+\frac{a-4-c_4}{b}}{|I_1|+|I_2|+|T_0|+l}$ arrives at the maximum value when $|I_1|+|I_2|+|T_0|+l$ reaches the lower bound $2n_{a,b}-2$. We deduce $\begin{array}{rl}I(G)& \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-4}{b}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-4}{(n_{a,b}-1)a}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n+1}{2n_{a,b}-2},\end{array}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}$ and $n_{a,b}\ge 2$.

Case 2. $|T_0|+l=0$.

Akin to Case 1, we verify that $H_1$ or $H_2$ can not exist independently.

Claim 3.3

If $|T_0|+l=0$, then $|I_2|\ne 0$.

Proof.

Suppose $|I_2|=0$. Then, we obtain $|I_1|\ne 0$, $|V(T)|=|V(H_1)|$ and $b|S|\le a|T|-d_{G-S}(T)+bn-1=|T|+bn-1$.

If $|I_1|=1$, then $|T|\le a-1$ and $|S|\le \frac{|T|+bn-1}{b}\le n+\frac{a-2}{b}$. Thus, $|S|=n$ contradicts to Observation 3.1. Hence, $|I_1|\ge 2$.

In this case, $i(G-U)\ge |I_1|\ge 2$ where $U=S\cup C_1\cup (N_G(I_1)\cap W)$, and using the deduction in Claim 3.1, we get $\begin{array}{rl}|S|& \le (\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|-\frac{1}{b}+n<\frac{a|I_1|}{b}+n,\\ |U|& \le |S|+|C_1|+\sum _{i=1}^k(i-1)|I^{(i)}|\le (a-1+\frac{a-1}{b})|I_1|+n-\frac{1}{b}\\ & \le (a-1+\frac{a}{b})|I_1|+n-\frac{3}{b}.\end{array}$ Using Observation 3.1, we deduce $|I_1|>\frac{b}{a}$ which implies $|I_1|\ge n_{a,b}$.

Hence, $I(G)\le \frac{|U|}{i(G-U)}\le \frac{\lfloor (a-1+\frac{a}{b})|I_1|+n-\frac{3}{b}\rfloor }{|I_1|}=a-1+\frac{n+\lfloor \frac{a|I_1|-3}{b}\rfloor }{|I_1|}.$ Let $a|I_1|-3=m_{5}b+c_5$, where $m_5\in \mathbb{N}\cup \{0\}$ and $c_5\in \{0,\dots ,b-1\}$. Then, we acquire $\begin{array}{rl}a-1+max\left\{\frac{\lfloor \frac{a|I_1|-3}{b}\rfloor +n}{|I_1|}\right\}& =a-1+max\left\{\frac{\frac{a|I_1|-3-c_5}{b}+n}{|I_1|}\right\}\\ & =a-1+\frac{a}{b}+max\left\{\frac{n-\frac{3+c_5}{b}}{|I_1|}\right\}.\end{array}$ If $\frac{n-\frac{3+c_5}{b}}{|I_1|}$ is negative, then n = 1 and $I(G)<a-1+\frac{a}{b}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $\frac{n-\frac{3+c_5}{b}}{|I_1|}$ is a non-negative term and it arrives at the maximum value when $|I_1|$ reaches its lower bound $n_{a,b}$. We infer $I(G)\le a-1+\frac{\lfloor \frac{a{n}_{a,b}-3}{b}\rfloor +n}{n_{a,b}}\le a-1+\frac{\lfloor \frac{a{n}_{a,b}-3}{(n_{a,b}-1)a}\rfloor +n}{n_{a,b}}\le a-1+\frac{n+1}{n_{a,b}},$ which contradicts to the hypothesis of isolated toughness.

Claim 3.4

If $|T_0|+l=0$, then $|I_1|\ne 0$.

Proof.

Suppose $|I_1|=0$, then $|I_2|\ne 0$ and hence $a\ge 3$.

If $|I_2|=1$, then we set $d_{\min }=min\{d_{G-S}(v)|v\in H_2\}$ and $z\in V(H_2)$ such that $d_{G-S}(z)=d_{\min }$, thus $d_{\min }\in \{1,\dots ,a-2\}$. Hence, we deduce $\begin{array}{rl}b|S|& \le a|T|-d_{G-S}(T)+bn-1\le |T|(a-d_{\min })+bn-1,\\ |S|& \le \frac{|T|(a-d_{\min })+bn-1}{b}\le \frac{(a-1)(a-d_{\min })-1}{b}+n\end{array}$ and $\begin{array}{rl}& a+n\le \delta (G)\le d_{\min }+|S|\le d_{\min }+\frac{(a-1)(a-d_{\min })-1}{b}+n\\ & =\frac{a^2}{b}-\frac{a}{b}+\frac{(b-a+1)d_{\min }}{b}-\frac{1}{b}+n\\ & \le \frac{a^2}{b}-\frac{a}{b}+\frac{(b-a+1)(a-2)}{b}-\frac{1}{b}+n\\ & =a-2+n+\frac{2a-3}{b},\end{array}$ a contradiction.

Hence, we get $|I_2|\ge 2$. Let $v_1,v_2,\dots ,v_{|I_2|}$ be vertices in $I_2$ as defined in Claim 3.2, thus $d_{G-S}(v_1)\le a-2$ and $d_{G-S}(v_1)\le d_{G-S}(v_2)\le \cdots \le d_{G-S}(v_{|I_2|})$. We have $|V(T)|=|V(H_2)|$, $\begin{array}{rl}b|S|& \le a|T|-d_{G-S}(T)+bn-1\\ & \le \sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))+bn-1\end{array}$ and $|S|\le \frac{\sum _{i=1}^{|I_2|}(d_{G-S}(v_i)+1)(a-d_{G-S}(v_i))}{b}+n-\frac{1}{b}.$ We infer $i(G-U)\ge |I_2|\ge 2$ where $U=S\cup N_{G-S}(I_2)$, and in view of the discussion in Claim 3.2, we yield $|U|\le |S|+|N_{G-S}(I_2)|\le (a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}.$ It is noteworthy that, to maximise $|U|$, only one vertex in $I_2$ has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of $|I_2|$, we rewritten the upper bound of $|S|$: $\begin{array}{rl}|S|& \le \frac{(|I_2|-1)(a-1+1)(a-(a-1))+(a-2+1)(a-(a-2))}{b}+n-\frac{1}{b}\\ & \le \frac{a|I_2|+a-3}{b}+n.\end{array}$ According to Observation 3.2, we yield $2+n\le |S|\le \frac{a|I_2|+a-3}{b}+n,$ which implies $|I_2|\ge \frac{2b-a+3}{a}\ge \frac{2(n_{a,b}-1)a-a+3}{a}=2n_{a,b}-3+\frac{3}{a}$, and hence $|I_2|\ge 2n_{a,b}-2$.

Using the same fashion as presented before, we get $\begin{array}{rl}I(G)& \le \frac{|U|}{i(G-U)}\le \frac{\lfloor (a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}\rfloor }{|I_2|}\\ & =a-1+\frac{n-1+\lfloor \frac{a|I_2|+a-3}{b}\rfloor }{|I_2|}.\end{array}$ Let $a|I_2|+a-3=m_{6}b+c_6$, where $m_6\in \mathbb{N}\cup \{0\}$ and $c_6\in \{0,\dots ,b-1\}$. Then, we acquire $\begin{array}{rl}a-1+max\left\{\frac{n-1+\lfloor \frac{a|I_2|+a-3}{b}\rfloor }{|I_2|}\right\}& =a-1+max\left\{\frac{n-1+\frac{a|I_2|+a-3-c_6}{b}}{|I_2|}\right\}\\ & =a-1+\frac{a}{b}+max\left\{\frac{n-1+\frac{a-3-c_6}{b}}{|I_2|}\right\}.\end{array}$ If $\frac{n-1+\frac{a-3-c_6}{b}}{|I_2|}$ is negative, then n = 1 and $I(G)<a-1+\frac{a}{b}$, which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $\frac{n-1+\frac{a-3-c_6}{b}}{|I_2|}$ is a non-negative term and it arrives at the maximum value when $|I_2|$ reaches its lower bound $2n_{a,b}-2$. We infer $\begin{array}{rl}I(G)& \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-3}{b}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-3}{(n_{a,b}-1)a}\rfloor }{2n_{a,b}-2}\\ & =a-1+\frac{n+1}{2n_{a,b}-2},\end{array}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}$ and $n_{a,b}\ge 2$.

It verifies from Claim 3.3 and Claim 3.4 that $|I_1|\ge 1$, $|I_2|\ge 1$ and $a\ge 3$. We check that $i(G-U)\ge 2$ where $U=S\cup C_1\cup (N_G(I_1)\cap W)\cup N_{G-S}(I_2)$ and $\begin{array}{rl}|U|& \le |S|+|C_1|+|N_G(I_1)\cap W|+|N_{G-S}(I_2)|\\ & \le (a-1+\frac{a-1}{b})|I_1|+(a-1+\frac{a}{b})|I_2|+n-1+\frac{a-3}{b}\\ & \le (a-1+\frac{a}{b})(|I_1|+|I_2|)+n-1+\frac{a-4}{b}.\end{array}$ In terms of the similar deduction to Case 1, we confirm that $|I_1|+|I_2|\ge 2n_{a,b}-2$ by Observation 3.2 and re-computing the supper bound of $|S|$.

Therefore, we have $\begin{array}{rl}I(G)& \le \frac{|U|}{i(G-U)}\le \frac{\lfloor (a-1+\frac{a}{b})(|I_1|+|I_2|)+n-1+\frac{a-4}{b}\rfloor }{|I_1|+|I_2|}\\ & =a-1+\frac{n-1+\lfloor \frac{a(|I_1|+|I_2|)+a-4}{b}\rfloor }{|I_1|+|I_2|}.\end{array}$ Let $a(|I_1|+|I_2|)+a-4=m_{7}b+c_7$, where $m_7\in \mathbb{N}\cup \{0\}$ and $c_7\in \{0,\dots ,b-1\}$. Then, $\begin{array}{rl}max\left\{\frac{n-1+\lfloor \frac{a(|I_1|+|I_2|)+a-4}{b}\rfloor }{|I_1|+|I_2|}\right\}& =max\left\{\frac{n-1+\frac{a(|I_1|+|I_2|)+a-4-c_7}{b}}{|I_1|+|I_2|}\right\}\\ & =\frac{a}{b}+max\left\{\frac{n-1+\frac{a-4-c_7}{b}}{|I_1|+|I_2|}\right\}.\end{array}$ If $n-1+\frac{a-4-c_7}{b}$ is negative, we get n = 1 and $I(G)<a-1+\frac{a}{b}$, which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}\ge a-1+\frac{2}{\frac{b}{a}+1}$. Hence, $n-1+\frac{a-4-c_7}{b}$ is non-negative and $\frac{n-1+\frac{a-4-c_7}{b}}{|I_1|+|I_2|}$ arrives at the maximum value when $|I_1|+|I_2|$ reaches the lower bound $2n_{a,b}-2$. We deduce $\begin{array}{rl}I(G)& \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-4}{b}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n-1+\lfloor \frac{a(2n_{a,b}-2)+a-4}{(n_{a,b}-1)a}\rfloor }{2n_{a,b}-2}\\ & \le a-1+\frac{n+1}{2n_{a,b}-2},\end{array}$ which contradicts to $I(G)>a-1+\frac{n+1}{n_{a,b}}$ and $n_{a,b}\ge 2$.

Therefore, we complete the proof of Theorem 1.1.

4. Open problems

In this paper, we determine the sharp isolated toughness bound for a graph to be fractional $(a,b,n)$-critical. Since fractional $[a,b]$-factor is a specific case of the more general fractional factors. n the stage of computer network topology design, it needs to make a balance between network security and network construction cost. The denser the network, the greater the isolated toughness, the stronger the corresponding network's ability to resist attacks, and the stronger the network. However, such a high-density network requires high construction costs, which greatly increases the network construction and maintenance costs. The tight bound of the isolated toughness parameter of the fractional critical graph provides engineers an important reference index. The network constructed according to the tight bound can theoretically guarantee that data transmission can still be maintained when the network suffers certain damages, and at the same time ensure the minimum cost of network construction, thus cut the budget.

We raise the following problems for future studies (the concepts of all fractional factor and fractional $(g,f)$-factor can be referred to the other related papers, and we skip the detailed explanation here).

Problem 4.1

What is the tight isolated toughness bound for all fractional $(a,b,n)$-critical graphs?

Problem 4.2

What is the tight isolated toughness bound for fractional $(g,f,n)$-critical graphs?

Acknowledgments

We thank the reviewers for their constructive comments in improving the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work has been partially supported by National Natural Science Foundation of China [grant numbers 12161094, 12031018, 12161141003, 11931006].