![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A graph G is a fractional -critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional
-factor. In this paper, we determine the exact tight isolated toughness bound for fractional
-critical graphs. To be specific, a graph G is fractional
-critical if
and
, where
is an integer satisfies
. 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
-critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional
-critical graphs.
AMS:
1. Introduction
The graphs we discuss in this paper are simple and finite. Let G be a graph with vertex set and edge set
. We denote
and
(simply by
and
) as the degree and the neighbourhood of vertex v in G respectively, and
is the minimum degree of G which took the smallest value of
among all vertices. Let
be the subgraph of G induced by
. Denote
as the number of isolated vertices in G. The operator
in
means adding edges for all pairs of vertices between
and
. The notations and terminologies used but undefined in this paper can be referred to Bondy and Murty (Citation2008).
Let a, b, k be positive integers with , and
be an indicator function defined on the edge set. A fractional
-factor is a spanning subgraph consisting of edge set
such that
(1)
(1)
for any
. A graph G admits a fractional
-factor means there is an indictor function h meeting (Equation1
(1)
(1) ). For
, G is a fractional
-critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional
-factor. In particular, if a = b = k, then fractional
-factor and fractional
-critical graph are degenerated to fractional k-factor and fractional
-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. (Citation2001) which is stated as
if G is not a complete graph, and
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 (Citation2006) contended that a graph G admits a fractional k-factor if and
. Gao and Wang (Citation2017) determined that G is a fractional
-critical graph if
, where
and
. Gao et al. (Citation2022) proved the tight isolated toughness bound for a graph G to be fractional
-critical, i.e. G is a fractional
-critical graph if
and
, where
. Zhou (Citation2021) and Zhou, Liu, Xu (Citation2022) 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. (Citation2022), Chen et al. (Citation2022), Zhou, Wu, Bian (Citation2022), Zhou, Wu, Liu (Citation2022) and Zhou, Wu, Xu (Citation2022).
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 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
-critical, and our main conclusion is stated as follows which extends the previous result in Gao et al. (Citation2022).
Theorem 1.1
Let G be a graph, and a, b, n be positive integers with and
, where
is an integer. If
and
, then G is a fractional
-critical graph.
To be obvious, is tight for a graph G to be fractional
-critical in terms of the definition of fractional
-factor. The sharpness of
in Theorem 1.1 is showcased in the following instance.
Consider where a, b, n are positive integers with
, and
is an integer which is determined by the correlation
with
. We directly get
On the other hand, set
and
, we yield
Thus, G is not a fractional
-critical graph by means of Lemma 2.2.
By setting a = b = k in Theorem 1.1, and thus the following corollary is derived for fractional
-critical graphs.
Corollary 1.1
Gao et al., Citation2022
Let G be a graph, and
be integers. If
and
, then G is a fractional
-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 -critical graph is imperative to prove our main theorem which is determined by Liu (Citation2010).
Lemma 2.1
Liu, Citation2010
Let a, b and n be positive integers such that . Then a graph G is fractional
-critical if and only if
holds for any
with
, where
.
It is noteworthy that for a given subset S of , T is determined by S which can be rewritten by
. We emphasise that Lemma 2.1 has its equal expression which is manifested below.
Lemma 2.2
Liu, Citation2010
Let a, b and n be positive integers such that . Then a graph G is fractional
-critical if and only if
holds for any disjoint subsets
with
.
The following lemma is obtained by slightly revising the Lemma 2.2 in Liu and Zhang (Citation2008) in view of its proving process which presents the characteristic of independent sets and covering sets in specific settings.
Lemma 2.3
Liu & Zhang, Citation2008
Let G be a graph and let such that
for every
and no component of H is isomorphic to
where
and
is an integer. Then there exists an independent set I and the covering set
of H satisfying
and
where
for
and
.
The crux of our proofing strategy is to get the integer upper bound of (or
instead), with the aim to eliminate the decimal part of
and obtain the desired conclusion. Another crucial trick in the proof process is to get the lower bound of the denominator of isolated toughness (
, some terms may become zero in special cases). It is observed from the derivation in the next section that the lower bound of
depends on
, i.e. the correlation between a and b determines lower bound of denominator to maximise the
, and then we infer the contradiction.
3. Proof of theorem thm1.1
If G is complete, the result is directly yielded by means of . 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
-critical graph. By Lemma 2.2, there exist disjoint subsets S and T of
with
satisfying
(2)
(2)
We choose S and T such that
is minimum. Thus,
, and
for any
. Furthermore, due to
, we obtain the following observation.
Observation 3.1
.
Let l be the number of the components of which are isomorphic to
and let
. Let H be the subgraph inferred from
by deleting those l components isomorphic to
. Let
be a set of vertices that contains exactly a−1 vertices in each component of
in
.
If , then from (Equation2
(2)
(2) ) and Observation 3.1, we yield
, i.e.
which implies
and
. Thus,
. In light of the definition of isolated toughness, we deduce
and
Let
, where
and
. Then, by
and
, we infer
which implies that
arrives at the maximum value when
reaches its lower bound
. Hence,
which contradicts to
.
Hence, we have . Let
where
is the union of components of H which satisfies that
for each vertex
and
. By means of Lemma 2.3,
has a maximum independent set
and the covering set
such that
(3)
(3)
and
(4)
(4)
where
for
and
. Using the definition of H and
, we verify that each component of
has a vertex of degree at most a−2 in G−S. Clearly, if
, then
, and
can be selected by Algorithm 1 (Gao et al., Citation2022):
Moreover, we have the following observation due to and at least one vertex in
has degree at most a−2 in G−S.
Observation 3.2
If , then
.
Set and
. The subsequent discussion is divided into two situations.
Case 1. .
The following two claims confirm that or
can not exist independently.
Claim 3.1
If , then
.
Proof.
Suppose . Then
by
.
We partition into two subsets.
:
if there exists
such that
;
:
if there is no intersection between
and
.
We yield
and
In view of Observation 3.1, we deduce
which implies
.
Moreover,
and thus
Let
, where
and
. Then, we obtain
If n = 1 and
, then
is negative, thus
which contradicts to
. Hence,
is a non-negative term and
reaches the maximum value when
reaches its lower bound
. Therefore,
which contradicts to the hypothesis of
.
Claim 3.2
If , then
.
Proof.
Suppose . We yield
by
, and hence
.
Let be vertices in
such that
and
. Then
,
and
We acquire
where
and
It is clear to see that to acquire the extremum isolated toughness, we maximise
with the given number of
, and thus only one vertex in
has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of
, it is imperative to re-compute the upper bound of
as follows:
Using Observation 3.2, we infer
which implies
, and hence
.
In terms of the definition of isolated toughness, we verify
Let
, where
and
. Then, we infer
If
is negative, then n = 1 and
which contradicts to
. Hence,
is non-negative and
arrives at the maximum value when
reaches the lower bound
. We deduce
which contradicts to
and
.
From Claim 3.1 and Claim 3.2, we check ,
and
.
Denote as vertices in
as defined in Claim 3.2. Then
,
and
We acquire
where
and
Similar to the discussion in Claim 3.2, to maximise
, only one vertex in
has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of
, it is necessary to re-calculate the upper bound of
:
By means of Observation 3.2, we yield
which implies
, and hence
.
Using the definition of , we obtain
Let
, where
and
. Then,
If
is negative, we get n = 1 and
, which contradicts to
. Hence,
is non-negative and
arrives at the maximum value when
reaches the lower bound
. We deduce
which contradicts to
and
.
Case 2. .
Akin to Case 1, we verify that or
can not exist independently.
Claim 3.3
If , then
.
Proof.
Suppose . Then, we obtain
,
and
.
If , then
and
. Thus,
contradicts to Observation 3.1. Hence,
.
In this case, where
, and using the deduction in Claim 3.1, we get
Using Observation 3.1, we deduce
which implies
.
Hence,
Let
, where
and
. Then, we acquire
If
is negative, then n = 1 and
which contradicts to
. Hence,
is a non-negative term and it arrives at the maximum value when
reaches its lower bound
. We infer
which contradicts to the hypothesis of isolated toughness.
Claim 3.4
If , then
.
Proof.
Suppose , then
and hence
.
If , then we set
and
such that
, thus
. Hence, we deduce
and
a contradiction.
Hence, we get . Let
be vertices in
as defined in Claim 3.2, thus
and
. We have
,
and
We infer
where
, and in view of the discussion in Claim 3.2, we yield
It is noteworthy that, to maximise
, only one vertex in
has degree a−2 in G−S and others have degree a−1 in G−S. To bound the value of
, we rewritten the upper bound of
:
According to Observation 3.2, we yield
which implies
, and hence
.
Using the same fashion as presented before, we get
Let
, where
and
. Then, we acquire
If
is negative, then n = 1 and
, which contradicts to
. Hence,
is a non-negative term and it arrives at the maximum value when
reaches its lower bound
. We infer
which contradicts to
and
.
It verifies from Claim 3.3 and Claim 3.4 that ,
and
. We check that
where
and
In terms of the similar deduction to Case 1, we confirm that
by Observation 3.2 and re-computing the supper bound of
.
Therefore, we have
Let
, where
and
. Then,
If
is negative, we get n = 1 and
, which contradicts to
. Hence,
is non-negative and
arrives at the maximum value when
reaches the lower bound
. We deduce
which contradicts to
and
.
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 -critical. Since fractional
-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 -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 -critical graphs?
Problem 4.2
What is the tight isolated toughness bound for fractional -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
References
- Bondy, J., & Murty, U. (2008). R. graph theory [m]. Springer.
- Chang, Y., Gao, W., Chelli, K., & Muttar, A. K. (2022). Performance evaluation of college laboratories based on fusion of decision tree and bp neural network. Applied Mathematics and Nonlinear Sciences, 7(2), 1–14. https://doi.org/10.2478/amns.2022.1.00001
- Chen, K., Wang, X., Alghazzawi, D., & Yanfeng, W. (2022). Visualized calculation of regional power grid power data based on multiple linear regression equation. Applied Mathematics and Nonlinear Sciences, 7(1), 93–102. https://doi.org/10.2478/amns.2021.1.00054
- Gao, W., & Wang, W. (2017). New isolated toughness condition for fractional (g,f,n)-critical graphs. Colloquium Mathematicum, 147(1), 55–65. https://doi.org/10.4064/cm6713-8-2016
- Gao, W., Wang, W., & Chen, Y. (2022). Tight isolated toughness bound for fractional (k,n)-critical graphs. Discrete Applied Mathematics, 322, 194–202. https://doi.org/10.1016/j.dam.2022.08.028
- Liu, G., & Zhang, L. (2008). Toughness and the existence of fractional k-factors of graphs. Discrete Mathematics, 308(9), 1741–1748. https://doi.org/10.1016/j.disc.2006.09.048
- Liu, S. (2010). On toughness and fractional (g,f,n)-critical graphs. Information Processing Letters, 110(10), 378–382. https://doi.org/10.1016/j.ipl.2010.03.005
- Ma, Y.-H., & Liu, G.-Z. (2006). Fractional factors and isolated toughness of graphs. Mathematica Applicata, 19(1), 188–194.
- Yang, J., Ma, Y., & Liu, G. (2001). Fractional (g,f)-factors in graphs. Applied Mathematics Journal Chinese Universities Series A, 16(4), 385–390.
- Zhou, S. (2021). A result on fractional (a,b,k)-critical covered graphs. Acta Mathematicae Applicatae Sinica–English Series, 37(4), 657–664. https://doi.org/10.1007/s10255-021-1034-8
- Zhou, S., Liu, H., & Xu, Y. (2022a). A note on fractional id-[a, b]-factor-critical covered graphs. Discrete Applied Mathematics, 319, 511–516. https://doi.org/10.1016/j.dam.2021.03.004
- Zhou, S., Wu, J., & Bian, Q. (2022b). On path-factor critical deleted (or covered) graphs. Aequationes Mathematicae, 96(4), 795–802. https://doi.org/10.1007/s00010-021-00852-4
- Zhou, S., Wu, J., & Liu, H. (2022c). Independence number and connectivity for fractional (a,b,k)-critical covered graphs. RAIRO-Operations Research, 56(4), 2535–2542. https://doi.org/10.1051/ro/2022119
- Zhou, S., Wu, J., & Xu, Y. (2022d). Toughness, isolated toughness and path factors in graphs. Bulletin of the Australian Mathematical Society, 106(2), 195–202. https://doi.org/10.1017/S0004972721000952