![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this paper we show that if G is a connected graph such that ,
and
then
exists and
if and only if G is not super-
. We also obtain some other results.
KEYWORDS:
1 Introduction
We follow [Citation1, Citation14] for graph-theoretical terminology and notation not defined here. Throughout this paper, a graph always means a finite undirected graph without self-loops or multiple edges, where
is the vertex-set and
is the edge-set. For any two adjacent vertices u, v, use
or
to denote the edge incident with u and v. The edge-connectivity
of G is an important measurement for fault-tolarance of the networks, and the larger
or
is, the more reliable the network is. It is well known that
, where
is the minimum degree of G. As more refined indices than connectivity and edge-connectivity, super connectivity and super edge-connectivity were proposed in [Citation2, Citation3]. An edge set F (vertex set
) of graph G is called an m -restricted edge-cut (m -restricted cut) if
(
) is disconnected and each component of
(
) contains at least m vertices. In literature some authors use the terminology super vertex cut instead of 2-restricted cut.
(
) is the minimum size of all m-restricted edge-cuts (m-restricted cuts) and
where
is the set of edges with exactly one end vertex in U and G[U] is the subgraph of G induced by U. A graph G is
-graph if
. An
-graph is called super m-restricted edge-connected or simply super-
if every minimum m-restricted edge cut isolates one component G[U] with
. By the definition of
, we can see that
as long as these parameters exist. It is clear that
. Also we denote
by
and
by
(for more information see [Citation4–13, Citation16, Citation18]).
Let be n copies of
. We add a new vertex u and let u be adjacent to every vertex in
,
. The resulting graph is denoted by
. It can be verified that
has no
-restricted edge cuts. In [Citation17] Zhang and Yuan showed that if G is a connected graph which is not isomorphic to
, where
and
then G has a k-restricted edge cut and
for
.
Proposition 1.1.
[17, Theorem 1] Let G be a connected graph with order at least which is not isomorphic to any
with
. Then for any
, G has k-restricted edge cuts and
.
Let be a simple connected graph. The line graph of G, denoted by
, or L shortly, is a graph with the vertex-set
, and a vertex xy is adjacent to a vertex wz in L if and only if they are adjacent as edges in G.
Proposition 1.2.
[15, Theorem 2] Suppose that G has order at least four and G is not a star. Then if and only if G is not super-
.
2 Main results
The complete bipartite graph is usually called a claw and a graph that does not contain an induced claw is called claw-free. It is easy to see that every line graph is claw-free. With the similar arguments in the proof of Lemma 5 in [Citation15] we prove the following lemma.
Lemma 2.1.
Let G be a connected claw-free graph. Then contains exactly two components for any minimum m-restricted cut S of G, where
.
Proof.
Suppose that S is a minimum m-restricted cut of G and are the connected components of
. Thus
contains at least
vertices, where
. Since S is a vertex-cut, there is a vertex
such that x is adjacent to every component, otherwise
is also a m-restricted cut, contradicting the minimality of S. If
the vertex x is adjacent to at least three components, which is impossible as G is a claw-free graph. Therefore,
and the lemma holds. ▪
Lemma 2.2.
Suppose that G is a graph and . Then each of the following holds:
graph G is super-
if and only if
,
graph G is super-
if and only if
.
Proof.
First suppose that G is super-
. Thus each minimum m-restricted edge-cut isolates a component of order m. We know that
. Let
and F be a minimum
-restricted edge-cut. Thus
and so F is minimum m-restricted edge-cut and isolate no component of order m, a contradiction. Now suppose that
. If G is not super-
then G has a minimum m-restricted edge-cut, say F, such that each component of
has order at least
. Thus
, a contradiction.
Proof is similar to Case
. ▪
In the rest of the paper we assume that G is triangle-free graph and . Thus it is easy to see that G is not isomorphic to
. Also for a subset
, we use
to denote the edge-induced subgraph of G by
.
Lemma 2.3.
Suppose that G is a graph and is a subgraph of
,
and
. If
is a connected subgraph of
with order at least 3 then the subgraph
is connected and
.
Proof.
Suppose that x and y are two distinct arbitrary vertices of . We show that there is a path from x to y. If
then the assertion holds. Thus, we may suppose that x is not adjacent to y and so x is adjacent to another vertex, say z. Let
, where
and
. Thus y is incident with another edge, say
. Let
. Now e and
are two edges in
and so are two vertices in
. Since
is connected it follows that there is a path, say P, between e and
. Let
. Now the corresponding edges
form a walk in
from x to y. We conclude that
is connected. Also since G is triangle-free graph, x is not adjacent to y,
and
we see that
. ▪
Theorem 2.4.
Suppose that G is a connected graph of order at least . Then
exists and
if and only if G is not super-
.
Proof.
By our assumption and by Proposition 1.1 we see that
exists. First suppose that G is not super-
. First we prove that
. Let S be a minimum 3-restricted cut of
. We know that
is claw free and so by Lemma 2.1
has exactly two components say,
and
. Also by Lemma 2.3,
is connected and
, where
is the edge-induced subgraph of G by
. Thus S is an 3-restricted edge cut of G. By our assumption about S, we have
. Now in the following we show that
. We know that G is not super-
. Thus there exists a minimum 3-restricted edge-cut, say F, such that no component of
has order 3. By our assumption we see that all components of
have order at least 4.
has at least two components. Suppose that C is an arbitrary component of
. Now
is connected and
. On the other hand, since F is an 3-restricted edge-cut in G then
is a component of
and F is a 3-restricted cut for
. Thus
exists and
.
Now suppose that exists and
. We show that G is not super-
. Suppose to contrary that G is super-
. Then each minimum 3-restricted edge-cut has an exactly one component of order 3. By considering
, there exists a 3-restricted cut S of
such that each component of
has order at least 3 and
. Thus
(*)
(*)
We know that is claw free and so by Lemma 2.1,
has exactly two components, say
and
. By Lemma 2.3,
where
and
. Since there is no path between
and
it follows that there is no path between
and
. Thus S is an 3-restricted edge cut of G and by
S is a minimum 3-restricted edge cut of G such that
has not component of order three, a contradiction. ▪
Theorem 2.5.
Suppose that G is a connected graph of order at least . Then
if and only if G is not super-
.
Proof.
By our assumption we see that G has at least 6 vertices, exists and G is not star. First suppose that G is not super-
. By Proposition 1.2, we see that
exists and
. Also since G is not super-
it follows that there is a minimum 2-restricted edge-cut, say F, such that
has no component of order 2 and
. By Lemma 2.2,
. Also by Theorem 2.4,
exists and
. Now by considering
and
we see that
and so
.
Conversely, suppose that . Assume that G is super-
. Thus each minimum 2-restricted edge cut isolates an edge. Let S be minimum 3-restricted cut of
such that
. Clearly each component of
has order at least three. We know that
is claw-free and so by Lemma 2.1,
has exactly two components, say
and
. Also by Lemma 2.3,
is connected and
. Thus S is an 2-restricted edge cut for G. Also since
we see that S is the minimum 2-restricted edge cut of G. But
contains no component of order 2, a contradiction. ▪
Theorem 2.6.
Suppose that G is a connected graph of order at least . Then
is super-
if and only if G is super-
.
Proof.
First suppose that is super-
. Suppose to contrary that G is not super-
. Then by Lemma 2.2, and Theorem 2.5, we have
and
. Also since
is super-
, again by Lemma 2.2, we have
. Moreover, since
is super-
, it follows that every minimum 2-restricted cut isolate a component of order 2. Let S be a minimum 2-restricted cut and
. Knowing that
is claw-free, by Lemma 2.1,
has exactly two components, say
and
. Also by Lemma 2.3,
is connected and
. Thus S is 3-restricted edge cut of G and so
. Therefore
Thus , a contradiction.
Conversely, suppose that G is super-. If
is not super-
then there exists a minimum 2-restricted cut of
, say S, such that each component of
has order at least three. Knowing that
is claw-free, by Lemma 2.1,
has exactly two components, say
and
. Also by Lemma 2.3,
is connected and
. Thus S is 3-restricted edge cut of G such that each component of
has order at least four. If S is minimum 3-restricted edge cut then by our assumption
should have a component of order three, a contradiction. Also if S is not minimum 3-restricted edge cut then there exists a minimum 3-restricted edge cut of G, say F, such that
. Clearly, F is a 2-restricted cut of
and this contradicts the minimality of S. ▪
Corollary 2.7.
Suppose that G is a connected graph of order at least . If G is not super-
, then
.
Proof.
Since G is not super-,
exists and
by Theorem 2.4. Also, by Theorem 2.6,
is not super-
. Now by Lemma 2.2,
and so
. ▪
References
- Bagga, J. S., Beineke, L. W. (2021). Line Graphs and Line Digraphs. Cham: Springer
- Bauer, D., Boesch, F., Suffel, C., Tindell, R. (1981). Connectivity extremal problems and the design of reliable probabilistic networks, In: Alavi, Y., Chartand, G., eds. The Theory and Application of Graphs. New York: Wiley, pp. 89–98.
- Boesch, F. T. (1986). Synthesis of reliable networks-A survey. IEEE Trans. Reliab. 35: 240–246.
- Esfahanian, A. H. (1989). Generalized measures of fault tolerance with application to n-cube networks. IEEE Trans. Comput. 38(11):1586–1591.
- Esfahanian, A. H., Hakimi, S. L. (1988). On computing a conditional edge-connectivity of a graph. Inf. Process. Lett. 27: 195–199.
- Kamyab, kh., Ghasemi, M., Varmazyar, R. Super connectivity of lexicographic product graphs. Ars Combinatoria, arXiv:2009.04831[math.GR] (accepted).
- Lu, M., Wu, C., Chen, G. L., Lu, C. (2008). On super connectivity of Cartesian product graphs. Networks 52: 78–87.
- Lü, M., Xu, J. M. (2006). Super connectivity of line graphs and digraphs. Acta. Math. Appl. Sin. Engl. Ser. 22: 43–48.
- Ning, W. T. (2020). Connectivity and super connectivity of the divide-and-swap cube. Theor. Comput. Sci. 842: 1–5.
- Ning, W. T. (2016). The super connectivity of exchanged crossed cube. Inf. Process. Lett. 116: 80–84.
- Soliemany, F., Ghasemi, M., Varmazyar, R. (2021). Super connectivity of a family of direct product graphs. Int. J. Comput. Math. Comput. Syst. Theory. 7(1): 1–5.
- Soliemany, F., Ghasemi, M., Varmazyar, R. (2022). On the super connectivity of direct product of graphs. RAIRO-Oper. Res. 56(4):2767–2773.
- Tian, Y. Z., Meng, J. X. (2015). Restricted connectivity for some interconnection networks. Graphs Comb. 31(5): 1727–1737.
- Xu, J. M. (2001). Topological Structure and Analysis of Interconnection Networks. Dordrecht: Kluwer Academic Publishers.
- Xu, J. M., Ma, M., Hellwig, A. (2005). Super connectivity of line graphs. Inf. Process. Lett. 94(4): 191–195.
- Wang, W. H., Zhang, Z., Qin, C. G., Guo, X. F. (2011). On super 2-restricted and 3-restricted edge-connected vertex transitive graphs. Discrete Math. 311: 2683–2689.
- Zhang, Z., Yuan, J. (2005). A proof of an inequality concerning k-restricted edge connectivity. Discrete Math. 304: 128–134.
- Zhang, Z., Meng, J. (2006). On optimally-λ3 transitive graphs. Discrete Appl. Math. 154: 1011–1018.