1. Introduction
The traditional connectivity and edge-connectivity, are important measures for networks, which can correctly reflect the fault tolerance of systems with few processors, but it always underestimates the resilience of large networks. The discrepancy incurred is because events whose occurrence would disrupt a large network after a few processors, therefore, the disruption envisaged occurs in a worst case scenario. To overcome such a shortcoming, Latifi et al. [1] proposed a kind of conditional edgeconnectivity, denoted by
, which is the minimum size of edge-cut
such that each vertex has degree at least
in
.
Throughout the paper graphs are undirected finite connected without loops or multiple edges.
Let
be a graph, an edge set
is a cyclic edge-cut if
is disconnected and at least two of its components contain cycles. Clearly, a graph has a cyclic edge-cut if and only if it has two vertexdisjoint cycles. A graph
is said to be cyclically separable if
has a cyclic edge-cut. Note that Lovász [2] characterized all multigraphs without two vertex-disjoint cycles. The characterization can also be found in Bollobás [3]. So, it is natural to further study the cyclically separable graphs. For a cyclically separable graph
, The cyclic edge-connectivity of
, denoted by
, is defined as the minimum cardinality over all cyclic edgecuts of
by following Plummer [4]. The concept of cyclic edge-connectivity as applied to planar graphs dates to the famous incorrect conjecture of Tait [5].
The cyclic edge-connectivity plays an important role in some classic fields of graph theory such as Hamiltonian graphs (Máčajová and Šoviera [6]), fullerence graphs (Kardoš and Šrekovski [7]), integer flow conjectures (Zhang [8]), n-extendable graphs (Holton et al. [9]; Lou and Holton [10]), etc.
For two vertex sets
is the set of edges with one end in
and the other end in
. For any vertex set
,
is the subgraph of
induced by
,
is the complement of
. Clearly, if
is a minimum cyclic edge-cut, then both
and
are connected. We set
where
is the number of edges with one end in
and the other end in
. It has been proved in Wang and Zhang [11] that
for any cyclically separable graph. Hence, a cyclically separable graph G is called cyclically optimal, in short,
, if
, and super cyclically edge-connected, in short,
, if the removal of any minimum cyclic edge-cut of graph
results in a component which is a shortest cycle.
Cyclic edge-fragment and cyclic edge-atom play a fundamental role. A vertex set
is a cyclic edgefragment, in short, fragment, if
is a minimum cyclic edge-cut. A cyclic edge-fragment with the minimum cardinality is called a cyclic edge-atom, in short, atom. A cyclic edge-fragment of
is said to be super, if neither
nor
induces a shortest cycle, in short, super fragment. A super cyclic edge-fragment with the minimum cardinality is called a super cyclic edge-atom, in short, super atom. A cyclic edge-fragment is said to be trivial, if it induces a cycle, otherwise it is nontrivial.
A graph
is said to be vertex transitive if
acts transitively on
, and is edge transitive if
acts transitively on
. A bipartite graph is biregular, if all the vertices from the same partite set have the same degree. We abbreviate the bipartite graph as a
-biregular graph, if the two distinct degrees are
and
respectively
. A bipartite graph
with bipartition
is called half vertex transitive [12], if
acts transitively both on
and
. Clearly, the half vertex transitive graph is biregular graph. Let
, we call the set ![](https://www.scirp.org/html/13-7401198\a1019c23-2e15-4019-b32c-3d40c6b53c65.jpg)
an orbit of
. Clearly,
acts transitively on each orbit of
. Transitive graphs have been playing an important role in designing network topologies, since they possess many desirable properties such as high fault tolerance, small transitive delay, etc. [13,14].
In Nedela and Škoviera [15], it was proved that a cubictransitive or edge-transitive graph (expect for
and
) is
-optimal. From Wang and Zhang [11], Xu and Liu [16], we have known that a
-regular vertex-transitive graph
is
-optimal if it has girth
. It was also shown that an edge-transitive graph
with minimum degree
and order
is
-optimal in Wang and Zhang [11]. Recently, Zhang and Wang [17] showed that a connected vertextransitive or edge-transitive graph is super-
if either
is cubic with girth
or G has minimum degree
and girth
. Zhou and Feng [18] characterized all possible
-superatoms for
- optimal nonsuper-
graphs, and classified all
-optimal nonsuper-
edge-transitive graphs.
Theorem 1.1 ([19]) Let G be a
-regular connect half vertex transitive graph with bipartition
, and girth
, then G is
-optimal.
Motivated by the work in Tian and Meng [19], in this article we aim to study a connected half vertex transitive graph, and we show that a connected half vertex transitive graph
is super cyclically edge-connected if minimum degree
and girth
.
2. Preliminaries
Lemma 2.1 ([11]) Let G be a simple connected graph with
and
or
and order
. Then G is cyclically separable.
Lemma 2.2 ([11]) Let G be a cyclically separable (p, q)-biregular graph with
. Suppose G is not cyclically optimal and
. Then for any distinct atoms X and Y,
.
An imprimitive block of
is a proper nonempty subset
of
such that for any automorphism
, either
or
.
Lemma 2.3 ([20]) Let
be a graph and let Y be the subgraph of G induced by an imprimitive block A of G. If G is vertex-transitive, then so is Y. If G is edge-transitive, then A is an independent set of G.
If X is a super atom, and
is a proper subset of X such that
is a cyclic edge-cut and
is not a shortest cyclic, then
![](https://www.scirp.org/html/13-7401198\60b98add-ee9f-4ad3-999a-7d30bf0d2d5c.jpg)
The observation is used frequently in the proofs.
Lemma 2.4 ([11]) Let G be a connected graph with
and
be a fragment. Then
(1)
;
(2) If
, then
holds for any
;
(3) If
is not a cycle and
is a vertex in X with
, then
holds for any
;
(4) If
, and X is a non-trivial atom of Gthen
. Furthermore,
holds for any
. and
holds for any
.
Lemma 2.5 ([17]) Let G be a connected graph with
and
. Then G has two vertex-disjoint cycles and
.
Lemma 2.6 ([17]) Let G be a (p,q)-biregular graph with
and girth
. Suppose G is cyclically optimal but not super cyclically edge-connected. Then any two distinct super atoms X and Y of G satisfies
.
Lemma 2.7 Let G be a connected (p,q)-half vertex transitive graph with bipartition
,
and girth
. Suppose A is a atom of G and
. If G is not
-optimal, then
(1)
is a disjoint union of distinct atoms;
(2) Y is a
-half vertex transitive graph, where
.
Proof. Let
and
then
.
Since A is a
-atom, we have
.
(1) Since
and Aut(X) acts transitively both on
and
, each vertex of G lies in a
- atom. by Lemma 2.3, we have that
is a disjoint union of distinct
-atoms.
(2) Let
, then there exits an automorphism
of G with
and so
. By Lemma 2.3,
. Thus the restriction of
on A induces an automorphism of Y, and then Aut(Y) acts transitively on
. Similarly, Aut(Y) acts transitively on
.
and
are two orbits of Aut(G). By (1), there exists
, such that
![](https://www.scirp.org/html/13-7401198\474cd0c1-e352-4d5d-9fb0-b8420c99d645.jpg)
Since Aut(G) has two orbits
and
, for any
and
,
and
. Thus, we have
,
, and
. Thus Y is a
-half vertex transitive graph, where
(by Lemma 2.4).
Lemma 2.8 ([17]) A cyclically optimal graph is not super cyclically edge-connected if and only if it has a super atom.
Lemma 2.9 Let G be a connected (p,q)-half vertex transitive graph with bipartition
and girth
. Suppose A is a super atom of G and
. If G is
-optimal but not super-
, then
(1)
is a disjoint union of distinct super atoms;
(2) Y is a
-half vertex transitive graph, where ![](https://www.scirp.org/html/13-7401198\ed7b8ddf-e6cf-4050-a613-65de793bdb50.jpg)
With a similar argument as the proof of Lemma 2.7, we can prove it.
3. Super-λc Half Vertex Transitive Graphs
Theorem 3.1 Let G be a connected (p,q)-half vertex transitive graph with bipartition
,
and girth
, then G is
-optimal.
Proof. By Lemma 2.1, G is cyclically separable. Suppose G is not
-optimal. By Lemma 2.2, every atom is impimitive block. Let A be a atom of G, by Lemma 2.3,
is half-vertex transitive. Let
and
, then
.
Suppose
is
by Lemma 2.4 (2),
. Let C be a shortest cycle of
. Then by Lemma 2.4 (2) and Lemma 2.5,
contains two disjoint cycles, and
is s cyclic edgecut. Clearly,
since no two vertices of C have common neighbor in
. Then,
![](https://www.scirp.org/html/13-7401198\7b64e157-8c78-460f-9872-6124ed889359.jpg)
a contradiction.
Theorem 3.2 Let G be a connected
-half vertex transitive graph with bipartition
,
and girth
, then G is super-
.
Proof. By Theorem 3.1, G is
-optimal. Suppose G is not super-
. By Lemma 2.8, G has a super atom. By Lemma 2.9, every super atom is impimitive block. Let A be a super atom of G, by Lemma 2.3,
is halfvertex transitive. Let
and
then
. Suppose
is
by Lemma 2.4 (2),
. Let C be a shortest cycle of
. With a similar proof as Theorem 3.1, we can get
, a contradiction.
4. Acknowledgements
We would like to appreciate the anonymous referees for the valuable suggestions which help us a lot in refining the presentation of this paper.
NOTES
#Corresponding author.