![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A graph G is called a -factor deleted graph if G – e has a
-factor for any
A graph G is
-factor critical deleted if for every subset
with
the graph
is
-factor deleted. Zhou, Bian and Pan [Discrete Appl. Math. (2021) in press] showed that an
-connected graph G is
-factor critical deleted if its binding number
In this paper, we give a new binding number condition for
-factor critical deleted graphs, which improves the above result.
Mathematics Subject Classification:
1. Introduction
In this paper, we deal with only finite simple graph. For standard graph-theoretic notation not explained here, we refer to [Citation4]. Given a vertex v in graph G, let be the set of vertices adjacent to v in G and
be the degree of v in G. For any subset
we define
by
and let
denote the subgraph of G induced by S. Denote by
the resulting graph after deleting the vertices of S from G. The concept of binding number was introduced by Woodall [Citation14]. For a connected graph G, its binding number, denoted by bind(G), was defined as
For a family of connected graphs a spanning subgraph H of a graph G is called an
-factor of G if each component of H is isomorphic to some graph in
A spanning subgraph H of a graph G is called a
-factor of G if every component of H is isomorphic to a path of order at least k. For example, a
-factor means a graph factor in which every component is a path of order at least three. A graph G is
-factor deleted if for every edge
G has a
-factor that excludes e. A graph G is
-factor critical deleted if for every subset
with
the graph
is
-factor deleted. Clearly, a
-factor critical deleted graph is a
-factor deleted graph.
The concept of sun was introduced by Kaneko [Citation6]. A graph H is called factor-critical if H – v has a 1-factor for each Let H be a factor-critical graph and
By adding new vertices
together with new edges
to H, the resulting graph is called a sun (e.g., see ). We also regard K1 and K2 as suns. A sun other than K1 is called a big sun. Obviously, the order of a big sun is at least 6. A component of G is called a sun component if it is isomorphic to a sun. We denote by sun(G) the number of sun components in G. Recently, Kaneko [Citation6] acquired a criterion for a graph to contain a
-factor, for which Kano, Katona and Király [Citation7] presented a simpler proof.
Theorem 1.1.
(Kaneko [Citation6]) A graph G has a -factor if and only if
for all
Since Tutte proposed the well-known Tutte 1-factor theorem [13], there are many results on graph factors [Citation1–3, Citation5, Citation9, Citation16, Citation20], which can be found in the survey paper [Citation12] and book [Citation15].
In this paper, we mainly focus on the relationship between binding number and path factors, which were investigated by Kano & Tokushige [Citation8], Nam [Citation10], Zhou et al. [Citation19], Robertshaw & Woodall [Citation11] and Zhou & Sun [Citation18].
Recently, Zhou, Bian and Pan [Citation17] obtained a binding number condition for an -connected graph to be
-factor critical deleted.
Theorem 1.2.
(Zhou, Bian and Pan [Citation17]) Let n be a nonnegative integer, and let G be an -connected graph. If
, then G is
-factor critical deleted.
In this paper, we also consider the binding number condition for an -connected graph to be
-factor critical deleted, which improves the result in the above Theorem.
Theorem 1.3.
Let n be a nonnegative integer. An -connected graph G is
-factor critical deleted if
2. Proof of Theorem 1.3
For any with
we write
To prove Theorem 1.3, it suffices to prove that
contains a
-factor for any
Suppose on the contrary that there exists an edge
such that
has no
-factor. Then by Theorem 1.1, there exists a subset
such that
(1)
(1)
Claim 2.1.
Proof.
Assume that On one hand, since
is a 2-connected graph and
Thus H is a connected graph, and
where
denotes the number of connected components of H. On the other hand, it follows from (1) that
Hence,
(2)
(2)
Note that Combining this with (2) implies that H is a big sun and
Let R be the factor-critical graph of H. Then
and there exists
such that
Obviously, u is a cut-vertex of
contradicting to
□
Claim 2.2.
and
Proof.
On the contrary, from Claim 2.1, we assume that Since G is
-connected,
It follows that
is a connected graph, i.e.,
Then by the definition of H, we have
(3)
(3)
On the other hand, according to (1),
contradicting to (3). Hence, and
□
Suppose that there exist a isolated vertices, b K2’s and c big sun components in H – X. We have
It follows from Claim 2.2 that
(4)
(4)
Claim 2.3.
and
Proof.
Suppose on the contrary that or
It follows from (4) that
Set
Then
and
Thus, we obtain that
which implies that
(5)
(5)
In terms of (4), (5), and
we can deduce that
which implies that
a contradiction. □
Next, we will consider the following two cases to complete the proof of Theorem 1.3.
Case 1.
and
Using the following rules, we construct a set Z such that and
If
or
without loss of generality, we can assume that
and choose
If
or
without loss of generality, we can assume that
Let Ri be the factor-critical subgraph of Hi. Choose
where
If
and
choose
Then we can obtain that
which implies that
(6)
(6)
In terms of (4), (6), and
we deduce that
which implies that
a contradiction to Claim 2.2.
Case 2.
or
Without loss of generality, we can assume that which implies that
Set
Then
and
We can obtain that
(7)
(7)
Subcase 2.1. n = 0.
According to the binding number condition and (7), we have
This together with and (4) implies that
which means
a contradiction to Claim 2.2.
Subcase 2.2.
According to the binding number condition and (7), we have
Together with and (4), we deduce that
which implies that
also a contradiction to Claim 2.2.
This completes the proof of Theorem 1.3. □
3. Remarks
In this paper, we obtain a new binding number condition to guarantee an -connected graph to be
-factor critical deleted. We think the lower bound c of binding number could be improved to some extent. Furthermore, it should satisfy the following property.
If we construct an
-connected graph
where
means “join”. Then
where
Note that
if
and
if n = 0. Set
and
For
we can deduce that
By Theorem 1.1, H does not contain a
-factor. Hence,
is not a
-factor deleted graph, i.e., G is not a
-factor critical deleted graph.
If we also construct an
-connected graph
Then
Set
and
For
we can deduce that
By Theorem 1.1, H does not contain a
-factor. Hence,
is not a
-factor deleted graph, which implies that G is not a
-factor critical deleted graph.
Additional information
Funding
References
- Dai, G. (2020). The existence of path-factor covered graphs. Discuss. Math. Graph Theory. https://doi.org/10.7151/dmgt.2353.
- Dai, G, Hu, Z. (2020). P3-factors in the square of a tree. Graphs Combinat. 36(6): 1913–1925.
- Dai, G., Zhang, Z., Hang, Y, Zhang, X. (2021). Some degree conditions for P≥3-factor covered graphs, RAIRO-Oper. Res., 55: 2907–2913.
- Diestel, R. (2005). Graph Theory, 3rd ed. Berlin: Springer.
- Hua, H. (2021). Toughness and isolated toughness conditions for P≥3-factor uniform graphs, J. Appl. Math. Comput. 66: 809–821.
- Kaneko, A. (2003). A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory Ser. B 88(2): 195–218.
- Kano, M., Katona, G. Y, Király, Z. (2004). Packing paths of length at least two. Discr. Math. 283(1-3): 129–135.
- Kano, M, Tokushige, N. (1992). Binding numbers and f-factors of graphs. J. Combin. Theory Ser. B 54(2): 213–221.
- Liu, H. (2022). Binding number for path-factor uniform graphs. Proc. Romanian Acad. Ser. A: Math. Phys. Tech. Sci. Inform. Sci. 23(1): 25–32.
- Nam, Y. (2010). Binding numbers and connected factors. Graphs Combin. 26(6): 805–813.
- Robertshaw, A, Woodall, D. (2002). Binding number conditions for matching extension. Discr. Math. 248(1-3): 169–179.
- Plummer, M. D. (2007). Perspectives: Graph factors and factorization: 1985-2003: A survey. Discr. Math. 307(7-8): 791–821.
- Tutte, W. T. (1952). The factors of graphs. Can. J. Math. 4: 314–328.
- Woodall, D. (1973). The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15(3): 225–255.
- Yu, Q, Liu, G. (2009). Graph Factors and Matching Extensions, Beijing: Springer Press.
- Zhou, S. Path factors and neighborhoods of independent sets in graphs. Acta Math. Appl. Sin. English Ser. https://doi.org/10.1007/s10255-022-1096-2.
- Zhou, S., Bian, Q, Pan, Q. (2021). Path factors in subgraphs. Discr. Appl. Math. https://doi.org/10.1016/j.dam.2021.04.012.
- Zhou, S, Sun, Z. (2020). Some existence theorems on path factors with given properties in graphs. Acta Math. Sin-English. Ser. 36(8): 917–928.
- Zhou, S., Wu, J, Bian, Q. (2021). On path-factor critical deleted (or covered) graphs. Aequat. Math. https://doi.org/10.1007/s00010-021-00852-4.
- Zhou, S., Wu, J, Xu, Y. (2021). Toughness, isolated toughness and path factors in graphs. Bull. Aust. Math. Soc. 1–8. https://doi.org/10.1017/S0004972721000952.