505
Views
0
CrossRef citations to date
0
Altmetric
Articles

Minimum fundamental cycle basis of some bipartite graphs

, , , &

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 (nk)-regular balanced graphs with order 2n.

1 Introduction

All graphs in this paper are undirected and simple. Let G=(V,E) be a graph. Any subgraph H of G can be represented by an incidence vector xZ2|E| such that e is an edge of H if and only if xe=1. A cycle of G is a connected subgraph with all vertices of degree 2. The cycle space of G is the vector space spanned by the incidence vectors of the cycles in G over Z2. A cycle basis of G consists of some cycles which form a basis of the cycle space of G. If G is a connected graph with n vertices and m edges, then the cycle matrix corresponding to a cycle basis B is an m by mn+1 matrix whose rows are indexed by the edges of G and columns by the elements of B. 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 G consists of mn+1 cycles, and the dimension of the cycle space of G is mn+1.

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 B={C1,C2,,Cs} of a graph G is called fundamental (or FCB for short), if there exists some spanning tree T of G such that B={CT(e)|eE(G)E(T)}, where CT(e) denotes the unique cycle in T{e}. 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 G and H is the graph G×H whose vertex set is the Cartesian product V(G)×V(H) and whose edges are (w,x)(y,z) where wyE(G) and xzE(H). In Citation[6], the authors considered the direct product of a complete graph Kn with K2 ( which is an (n1)-regular balanced bipartite graph with order 2n), 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 (nk)-regular balanced graphs with order 2n, which is a generalization of Theorem 3 in Citation[6].

For a subset S of E(G), we denote by GS the subgraph of G obtained by deleting the edges of S. The neighborhood of a vertex v in G is the set NG(v)={wV(G)|vwE(G)}. The degree of a vertex v in G, denoted by dG(v), is |NG(v)|. If G is a bipartite graph with two parts X and Y, for any vX (or vY), we define NG(v)=YNG(v) (or NG(v)=XNG(v) ), and use dG(v) to denote the number of vertices in NG(v). If uv is an edge of the bipartite graph G, we denote muv the number of edges between NG(u) and NG(v).

If G is connected, the distance between vertices u and v, denoted by dG(u,v), is the length of a shortest path in G connecting them. The diameter of G, denoted by d(G), is the largest distance of G. For a cycle basis B of G, we use m6(B) to denote the number of cycles of length 6 in B.

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 T of G is centralized, if there exists an edge v1v2 of T which satisfies the following two conditions:

1.

NT(vi)=NG(vi), where i=1,2;

2.

the distance between vi and any other vertex (if exists) in the same part of T is 2, where i=1,2.

v1v2 is called a key edge of T.

If T is a centralized spanning tree, the diameter of T 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 G to denote the set of all bipartite graphs with centralized spanning trees, T(G) to denote the set of all centralized spanning trees of G, and K(T) to denote the set of all key edges of the centralized spanning tree T. For convenience, for any GG, we define N(G)=minuvK(T)TT(G)muv.If G has a centralized spanning tree T such that d(T)4, it is not difficult to see that for any key edge uv, NG(u) or NG(v) is empty, so there is no edge between NG(u) and NG(v), and then muv=0, which implies that N(G)=0. So for a bipartite graph GG, N(G)=0,ifGhas a centralized spanning treeTwithd(T)4;minTT(G)muv,otherwise.

Let G be a connected bipartite graph and let vG. If N(G)=, then we say that v is saturated. Otherwise v is unsaturated.

Since G is bipartite, the lengths of its cycles are at least 4. In the following lemma we will show that for any FCB of GG 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 GG, andB be a fundamental cycle basis of G corresponding to a centralized spanning tree T, then

1.

B does not contain any cycle of length more than 6,

2.

m6(B)=muv, where uv is a key edge of T.

Proof

1.

Note that d(T)5, so there is no cycle with length more than 6 in the corresponding FCB produced by T.

2.

Let V=NG(u)NG(v), where uvK(T). We consider two cases. Case 1 u or v is saturated. Then the induced subgraph of V is empty (without edges), and the diameter of T is no more than 4. Hence, there is no any cycle of length 6 in B, i.e., m6(B)=0, and thus the equality holds. Case 2 Neither u nor v is saturated. Let V1, V2 be the two parts of G. Without loss of generality, we suppose uV1, vV2. Then V1 can be divided into three disjoint parts {u},NG(v){u} and NG(v). Similarly, V2 can be divided into three disjoint parts {v},NG(u){v} and NG(u). It is not difficult to check that only the distances between the vertices in NG(u) and the vertices in NG(v) are 5. If we add one edge of G between NG(u) and NG(v) to T, we will obtain a cycle of length 6. Hence, m6(B)=muv. __

Lemma 2.2

Let GG, and T be the corresponding spanning tree of an MFCB. If for any two verticess,t in the same part of G, (1) NG(s)NG(t)>max{2,N(G)}+1(1) holds, then there does not exist any path of length 6 inT.

Proof

Let V1, V2 be the two parts of G, and B be the MFCB produced by T. Suppose that T contains a path P of length 6. With no loss of generality, let P=a1b1a2b2a3b3a4, and {a1,a2,a3,a4}V1, {b1,b2,b3}V2. Obviously, TE(P) has 7 components. For uV(P), we use Tu to denote the component containing u of TE(P). Let W=(NG(a1)NG(a4)){b1,b2,b3}, from the inequality (1), we have W|NG(a1)NG(a4)|3>max{2,N(G)}20. So W is non-empty. To prove the result, we show the following claim first.

Claim There are at least W cycles of length at least 6 in B.

Since W is non-empty, there are at least one component of TE(P), say Tx (where xV(P)), shares common vertices with W.

Let βV(Tx)W. Note that 6=dT(a1,a4)=dT(a1,x)+dT(x,a4). If dT(a1,x)dT(x,a4), i.e., dT(a1,x)3 and x{b2,b3,a3,a4}. From the definition of W, we know βa1 is an edge of G.

We consider the case x{b2,b3} first. It is not difficult to find that dT(β,a1)=dT(β,x)+dT(x,a1)5 since both β and x are in V2 which yields dT(β,x)=dTx(β,x)2. Now adding the edge βa1 to T, it will produce a cycle of length at least 6 in B. And then, m6(B)W.

If x{a3,a4}. Observe that dT(a1,x)3 for x and a1 are in the same part of bipartite graph, so we have dT(a1,x)4. Then dT(β,a1)=dT(β,x)+dT(x,a1)5. If adding the edge βa1 to T, then it will form a cycle of length at least 6 in B. In this case, we also have m6(B)W.

If dT(a1,x)<dT(x,a4), by adding the edge βa4 to T, 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 G) in {a1b3,a4b1} to T. Let {b1,b3}(NG(a1)NG(a4))=k (where k is 0, 1 or 2), then NG(a1)NG(a4){b1,b3}=2k. Combining these with the above claim, we can conclude that B contains at least |W|+2k cycles of length at least 6. By the definition of W, we have Wk+2=NG(a1)NG(a4){b1,b2,b3}k+2=NG(a1)NG(a4)NG(a1)NG(a4){b1,b2,b3}k+2NG(a1)NG(a4)NG(a1)NG(a4){b1,b3}k+1=NG(a1)NG(a4)1>max{2,N(G)}. From the above discussion, we know that MFCB contains more than N(G) cycles of length no less than 6. If the dimension of the cycle space of G is , then the length of B is more than 4+2N(G).

Note that G is a finite graph, by Lemma 2.1, there exists an FCB, say B, which contains no cycle of length more than 6, so the length of B is 4+2N(G), which contradicts to the fact that MFCB is an FCB with minimum length. __

Theorem 2.1

Let GG. If for any two vertices s,t in the same part of G, (2) NG(s)NG(t)>max{2,N(G)}+1(2) holds, then G has an MFCB whose corresponding spanning tree is centralized.

Proof

We consider two cases.

Case 1 There exists some vertex v of G is saturated.

If one neighbor of v is also saturated, then G has a spanning tree with diameter 3 which is centralized. By adding one edge of G to the spanning tree, we will obtain a cycle of length no more than 4. For G 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 v is unsaturated, then G has a spanning tree with diameter 4 which is also centralized. If we add one edge of G to the spanning tree, then we will obtain an FCB which contains only cycles of length 4. Since G is bipartite, we deduce that the obtained FCB is consequently an MFCB.

Case 2 All vertices of G are unsaturated.

Let B be an MFCB of G, and F be the corresponding spanning tree. By Lemma 2.2, the diameter of F is no more than 5. We first prove that the diameter is exactly 5.

It is not difficult to see that the diameter of F is not 3. Now suppose that the diameter is 4, and P=abcde is a longest path of F. By the definition of unsaturated vertex, there are some vertices of NG(c) not in F, which contradicts to the fact that F is a spanning tree. So the diameter of F is 5.

Let P=a1b1a2b2a3b3 be a longest path of F. Then m6(B) equals the number of edges in G between NF(a2) and NF(b2). Note that NF(a2)NG(a2) and NF(b2)NG(b2), we find that NG(a2)NF(a2) and NG(b2)NF(b2), which yield m6(B)ma2b2. In light of Lemma 2.1, B contains only cycles of length 4 and 6. Since the dimension of the cycle space is fixed, and B is an MFCB, so we have m6(B)=ma2b2, which yields that NF(a2)=NG(a2) and NF(b2)=NG(b2). Hence F is a centralized spanning tree. __

Theorem 2.2

Let GG. If for any two vertices s,t in the same part of G, (3) NG(s)NG(t)>max{2,N(G)}+1(3) holds, then G has an MFCB which consists of N(G) cycles of length 6 and the rest of length 4.

Proof

From the proof of Theorem 2.1, if there exists some vertex v of G is saturated, then G has an MFCB whose corresponding spanning tree with diameter less than 5, so N(G)=0, and the desired result holds. If all vertices of G are unsaturated, G has an MFCB with diameter 5, and m6(B)=ma2b2N(G). By Lemma 2.1, m6(B)N(G), and thus, m6(B)=N(G). _

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 GG be an(nk)-regular balanced bipartite graph with order 2n. If for any two vertices s,t in the same part of G satisfy NG(s)NG(t)>max{2,k2}+1,then any minimum fundamental cycle basis B of G consists ofm6(B) cycles of length 6 and the rest of length 4, and km6(B)k2.

Proof

It suffices to prove km6(B)k2.

Since G is a balanced (nk)-regular bipartite graph, for any edge uv, both NG(u) and NG(v) have k vertices, so muvk2, and thus N(G)=minuvK(T)TT(G)muvk2. Hence, NG(s)NG(t)>max{2,N(G)}+1 follows from NG(s)NG(t)>max{2,k2}+1.

By Theorem 2.2, the number of cycles of length 6 in B is N(G), i.e., m6(B)=N(G) , so it suffices to prove N(G)k. Observe that for any vertex α of NG(v), there are at most k1 vertices in NG(u) which are not adjacent to α, that is to say, NG(u) contains at least one neighbor of α. So there are at least k edges between NG(u) and NG(v). From the arbitrariness of uv, we know that N(G)k. _

Theorem 3.2

(1)

If G=Kn,n (where n>1), then any MFCB of G consists of only cycles of length 4.

(2)

If G is an (n1)-regular balanced bipartite graph with order 2n and n>5, then any MFCB of G consists of one cycle of length 6 and the rest of length 4.

(3)

If G is an (n2)-regular balanced bipartite graph with order 2n and n>9, then any MFCB of G consists of k cycles of length 6 and the rest of length 4, where k{2,3,4}.

Proof

(1) It is easy to check that the graph obtained from two stars K1,n1 by adding one edge between the centers is a centralized spanning tree of Kn,n, and thus GG. If n3, the result holds obviously. If n4, for any two vertices in the same part have n common neighbors, the desired result holds from Theorem 3.1.

(2) Let V1={u1,,un} and V2={v1,,vn} be the two parts of G. Without loss of generality, we suppose NG(u1)={v1,,vn1} and NG(v1)={u1,,un1}. Since n>2, there exist i,j{1,,n1} such that unviE(G) and vnujE(G). Then the tree with edge set {u1v1,u1v2,u1vn1,v1u2,,v1un1,unvi,vnuj} is a centralized spanning tree of G, i.e. GG. Note that any two vertices in the same part have at least n2>3=max{2,12}+1 common neighbors, so by Theorem 3.1, we get the result.

(3) Let V1={u1,,un} and V2={v1,,vn} be the two parts of G. Without loss of generality, we suppose NG(u1)={v1,,vn2} and NG(v1)={u1,,un2}. Since n>9, there exist i,j,i,j{1,,n2} such that {un1vi,unvi}E(G) and {vn1uj,vnuj}E(G). Then the tree with edge set {u1v1,,u1vn2,v1u2,,v1un2,un1vi,unvi,vn1uj,vnuj} is a centralized spanning tree of G, i.e. GG. Note that any two vertices in the same part have at least n4>5=max{2,22}+1 common neighbors, so by Theorem 3.1, we get the result. __

Since Kn×K2 is the (n1)-regular balanced bipartite graph with order 2n, 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