![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
We determine the number of cycles of different lengths in the minimum fundamental cycle basis of some bipartite graphs with centralized spanning trees. As applications, we characterize the minimum fundamental cycle basis of some -regular balanced graphs with order
.
1 Introduction
All graphs in this paper are undirected and simple. Let be a graph. Any subgraph
of
can be represented by an incidence vector
such that
is an edge of
if and only if
. A cycle of
is a connected subgraph with all vertices of degree 2. The cycle space of
is the vector space spanned by the incidence vectors of the cycles in
over
. A cycle basis of
consists of some cycles which form a basis of the cycle space of
. If
is a connected graph with
vertices and
edges, then the cycle matrix corresponding to a cycle basis
is an
by
matrix whose rows are indexed by the edges of
and columns by the elements of
. The length of a cycle basis is the sum of the lengths of the cycles in the basis. A minimum cycle basis (or MCB for short) of a graph is a cycle basis with minimum length. One can verify that any MCB of
consists of
cycles, and the dimension of the cycle space of
is
.
In Citation[1] five different classes of cycle basis are defined, namely: fundamental, weakly fundamental, totally unimodular, integral and undirected cycle basis. In this article, we just consider the fundamental cycle basis of some bipartite graphs.
Definition 1.1
A cycle basis of a graph
is called fundamental (or FCB for short), if there exists some spanning tree
of
such that
, where
denotes the unique cycle in
. A minimum fundamental cycle basis of a graph is a fundamental cycle basis with minimum length (or MFCB for short).
Although a minimum cycle basis of a graph can be computed in polynomial time Citation[2], but to give an explicit description of such a basis of some families of graphs seems hard. This problem is solved for some families of graphs, for example see Citation[3–6].
The direct product of graphs and
is the graph
whose vertex set is the Cartesian product
and whose edges are
where
and
. In Citation[6], the authors considered the direct product of a complete graph
with
( which is an
-regular balanced bipartite graph with order
), constructed a minimum fundamental cycle basis of the graph.
Motivated by their work, we consider the minimum fundamental cycle basis of some special bipartite graphs, determine the number of cycles of different lengths in their minimum fundamental cycle basis. As applications, we characterize the minimum fundamental cycle basis of some -regular balanced graphs with order
, which is a generalization of Theorem 3 in Citation[6].
For a subset of
, we denote by
the subgraph of
obtained by deleting the edges of
. The neighborhood of a vertex
in
is the set
. The degree of a vertex
in
, denoted by
, is
. If
is a bipartite graph with two parts
and
, for any
(or
), we define
(or
), and use
to denote the number of vertices in
. If
is an edge of the bipartite graph
, we denote
the number of edges between
and
.
If is connected, the distance between vertices
and
, denoted by
, is the length of a shortest path in
connecting them. The diameter of
, denoted by
, is the largest distance of
. For a cycle basis
of
, we use
to denote the number of cycles of length 6 in
.
2 MFCB of some bipartite graphs with centralized spanning trees
We begin this section with defining a special spanning tree of connected graph.
Definition 2.1
A spanning tree of
is centralized, if there exists an edge
of
which satisfies the following two conditions:
1. |
| ||||
2. | the distance between |
is called a key edge of
.
If is a centralized spanning tree, the diameter of
is no more than 5. A centralized spanning tree with diameter 5 has exactly one key edge, but, if the diameter is less than 5, the key edge maybe not unique. We use
to denote the set of all bipartite graphs with centralized spanning trees,
to denote the set of all centralized spanning trees of
, and
to denote the set of all key edges of the centralized spanning tree
. For convenience, for any
, we define
If
has a centralized spanning tree
such that
, it is not difficult to see that for any key edge
,
or
is empty, so there is no edge between
and
, and then
, which implies that
. So for a bipartite graph
,
Let be a connected bipartite graph and let
. If
, then we say that
is saturated. Otherwise
is unsaturated.
Since is bipartite, the lengths of its cycles are at least 4. In the following lemma we will show that for any FCB of
produced by a centralized spanning tree does not contain any cycle of length more than 6, and will determine the number of cycles of length 6 in the FCB.
Lemma 2.1
Let , and
be a fundamental cycle basis of
corresponding to a centralized spanning tree
, then
1. |
| ||||
2. |
|
Proof
1. | Note that | ||||
2. | Let |
Lemma 2.2
Let , and
be the corresponding spanning tree of an MFCB. If for any two vertices
,
in the same part of
,
(1)
(1) holds, then there does not exist any path of length 6 in
.
Proof
Let ,
be the two parts of
, and
be the MFCB produced by
. Suppose that
contains a path
of length 6. With no loss of generality, let
, and
,
. Obviously,
has 7 components. For
, we use
to denote the component containing
of
. Let
, from the inequality (1), we have
So
is non-empty. To prove the result, we show the following claim first.
Claim There are at least cycles of length at least 6 in
.
Since is non-empty, there are at least one component of
, say
(where
), shares common vertices with
.
Let . Note that
. If
, i.e.,
and
. From the definition of
, we know
is an edge of
.
We consider the case first. It is not difficult to find that
since both
and
are in
which yields
. Now adding the edge
to
, it will produce a cycle of length at least 6 in
. And then,
.
If . Observe that
for
and
are in the same part of bipartite graph, so we have
. Then
. If adding the edge
to
, then it will form a cycle of length at least 6 in
. In this case, we also have
.
If , by adding the edge
to
, we can get the claim similarly.
Now we continue the proof of the lemma. It is not difficult to see that, we can obtain a cycle of length 6 by adding one edge (if there exists in ) in
to
. Let
(where
is 0, 1 or 2), then
. Combining these with the above claim, we can conclude that
contains at least
cycles of length at least 6. By the definition of
, we have
From the above discussion, we know that MFCB contains more than
cycles of length no less than 6. If the dimension of the cycle space of
is
, then the length of
is more than
.
Note that is a finite graph, by Lemma 2.1, there exists an FCB, say
, which contains no cycle of length more than 6, so the length of
is
, which contradicts to the fact that MFCB is an FCB with minimum length. __
Theorem 2.1
Let . If for any two vertices
,
in the same part of
,
(2)
(2) holds, then
has an MFCB whose corresponding spanning tree is centralized.
Proof
We consider two cases.
Case 1 There exists some vertex of
is saturated.
If one neighbor of is also saturated, then
has a spanning tree with diameter 3 which is centralized. By adding one edge of
to the spanning tree, we will obtain a cycle of length no more than 4. For
is bipartite, the length of the cycle is 4, and thus the FCB produced by this spanning tree contains only cycles of length 4, so it is an MFCB.
If any neighbor of is unsaturated, then
has a spanning tree with diameter 4 which is also centralized. If we add one edge of
to the spanning tree, then we will obtain an FCB which contains only cycles of length 4. Since
is bipartite, we deduce that the obtained FCB is consequently an MFCB.
Case 2 All vertices of are unsaturated.
Let be an MFCB of
, and
be the corresponding spanning tree. By Lemma 2.2, the diameter of
is no more than
. We first prove that the diameter is exactly 5.
It is not difficult to see that the diameter of is not 3. Now suppose that the diameter is 4, and
is a longest path of
. By the definition of unsaturated vertex, there are some vertices of
not in
, which contradicts to the fact that
is a spanning tree. So the diameter of
is 5.
Let be a longest path of
. Then
equals the number of edges in
between
and
. Note that
and
, we find that
and
, which yield
. In light of Lemma 2.1,
contains only cycles of length 4 and 6. Since the dimension of the cycle space is fixed, and
is an MFCB, so we have
, which yields that
and
. Hence
is a centralized spanning tree. __
Theorem 2.2
Let . If for any two vertices
,
in the same part of
,
(3)
(3) holds, then
has an MFCB which consists of
cycles of length 6 and the rest of length 4.
Proof
From the proof of Theorem 2.1, if there exists some vertex of
is saturated, then
has an MFCB whose corresponding spanning tree with diameter less than 5, so
, and the desired result holds. If all vertices of
are unsaturated,
has an MFCB with diameter 5, and
. By Lemma 2.1,
, and thus,
. _
3 MFCB of regular balanced bipartite graph
In this section, we consider the MFCB of regular balanced bipartite graph with centralized spanning trees. A balanced bipartite graph is a bipartite graph whose two parts have equal cardinality.
Theorem 3.1
Let be an
-regular balanced bipartite graph with order
. If for any two vertices
,
in the same part of
satisfy
then any minimum fundamental cycle basis
of
consists of
cycles of length 6 and the rest of length 4, and
.
Proof
It suffices to prove .
Since is a balanced
-regular bipartite graph, for any edge
, both
and
have
vertices, so
, and thus
. Hence,
follows from
.
By Theorem 2.2, the number of cycles of length 6 in is
, i.e.,
, so it suffices to prove
. Observe that for any vertex
of
, there are at most
vertices in
which are not adjacent to
, that is to say,
contains at least one neighbor of
. So there are at least
edges between
and
. From the arbitrariness of
, we know that
. _
Theorem 3.2
(1) | If | ||||
(2) | If | ||||
(3) | If |
Proof
(1) It is easy to check that the graph obtained from two stars by adding one edge between the centers is a centralized spanning tree of
, and thus
. If
, the result holds obviously. If
, for any two vertices in the same part have
common neighbors, the desired result holds from Theorem 3.1.
(2) Let and
be the two parts of
. Without loss of generality, we suppose
and
. Since
, there exist
such that
and
. Then the tree with edge set
is a centralized spanning tree of
, i.e.
. Note that any two vertices in the same part have at least
common neighbors, so by Theorem 3.1, we get the result.
(3) Let and
be the two parts of
. Without loss of generality, we suppose
and
. Since
, there exist
such that
and
. Then the tree with edge set
is a centralized spanning tree of
, i.e.
. Note that any two vertices in the same part have at least
common neighbors, so by Theorem 3.1, we get the result. __
Since is the
-regular balanced bipartite graph with order
, Theorem 3 in Citation[6] is a special case of Theorem 3.2(2).
Acknowledgment
The authors are thankful to the referee for his/her valuable comments and suggestions which improved the presentation of the paper. Research supported by the National Natural Science Foundation of China (No. 11101284, 11201303 and 11301340).
References
- LiebchenChRizziR., Classes of cycle bases Discrete Appl. Math. 155 3 2007 337–355
- HortonJ.D., A polynomial-time algorithm to find the shortest cycle basis of a graph SIAM J. Comput. 161987 359–366
- BradshawZ.JaradatM.M.M., Minimum cycle bases for direct products of K2 with complete graphs Australas. J. Combin. 432009 127–131
- HammackR., Minimum cycle bases of direct products of complete graphs Inform. Process. Lett. 102 5 2007 214–218
- StadlerP., Minimum cycle bases of Halin graphs J. Graph Theory 43 2 2003 150–155
- GhareghaniN.KhosrovshahiG.B., Minimum cycle basis of direct product of K2×Kn Linear Algebra Appl. 4582014 671–678