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 
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
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
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 
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,
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.