Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 101–119
Minimum cycle bases of direct products
of graphs with cycles
Zachary Bradshaw ∗
Department of Mathematics and Applied Mathematics, Virginia Commonwealth
University, Richmond, VA, USA
Richard H. Hammack †
Department of Mathematics and Applied Mathematics, Virginia Commonwealth
University, Richmond, VA, USA
Received 17 July 2008, accepted 18 May 2009, published online 22 June 2009
Abstract
We construct a minimum cycle basis for the direct product G × Cq where G is a con-
nected non-bipartite graph, Cq is an odd cycle and G×Cq is triangle-free. These bases are
expressed in terms of the cycle structure of the symmetric digraph on G.
Keywords: Graph direct product, minimum cycle bases, digraphs.
Math. Subj. Class.: O5C38
1 Introduction
In the article Minimum Cycle Bases of Product Graphs [7], W. Imrich and P. Stadler con-
struct minimum cycle bases for Cartesian and strong products of graphs, in terms of mini-
mum cycle bases of the factors. F. Berger [1] and M. Jaradat [8] solve the same problem for
the lexicographical product. The corresponding construction for the direct product appears
to be extremely complex. The problem has been solved for the special cases where both
factors are bipartite [4] or complete graphs [2, 5]. The authors of the present paper have
an outline of a construction for a minimum cycle basis of the product G ×H where both
factors are arbitrary connected non-bipartite graphs (and at least one factor is triangle-free),
but the proofs are too long to be of much interest. In this paper we offer a scaled-back ver-
sion of the problem. We describe minimum cycle bases for G×Cq where G is a connected
non-bipartite graph and Cq is the odd cycle on q vertices.
∗Supported by the Virginia Commonwealth University Honors Summer Undergraduate Research Program.
†Corresponding author.
E-mail addresses: bradshawz@vcu.edu (Zachary Bradshaw), rhammack@vcu.edu (Richard H. Hammack)
Copyright c© 2009 DMFA
102 Ars Math. Contemp. 2 (2009) 101–119
We begin with a brief review of the preliminaries. The edge space E(G) of a simple
graph G = (V (G), E(G)) is the power set of its edges E(G) endowed with the structure
of a vector space over the two-element field F2 = {0, 1}. Addition in E(G) is symmetric
difference of sets, and zero is the empty set. To simplify notation, we blur the distinction
between subgraphs K of G and their edge set E(K) ∈ E(G). Thus, if J and K are
subgraphs, an expression such as J + K means E(J) + E(K), with the operation taking
place in E(G). With this convention, we regard E(G) as the set of all connected one-edge
subgraphs of G, so E(G) a basis for E(G). Similarly, the vertex space V(G) of G is the
power set of V (G) endowed with a vector space structure over F2. (Addition is symmetric
difference.) Bending the notation slightly (as was done for the edge space) we regard V (G)
as a basis for V(G).
The cycle space of G, denoted C(G), is the subspace of E(G) consisting of the edge
setsE(K) of Eulerian subgraphsK ofG, that is, subgraphs having no vertex of odd degree.
(See [3], Proposition 1.9.2). Elements of C(G) are called cycles. We call a cycle a simple
cycle if it is connected and each vertex has degree 2. The simple cycle with p edges is
denotedCp. The dimension of C(G) is the (first) Betti number β(G) = |E(G)|−|V (G)|+c,
where c is the number of components of G ([3], Theorem 1.9.6). A graph homomorphism
g : G → H induces a linear map g∗ : E(G) → E(H) defined on the basis E(G) as
g∗(vw) = g(v)g(w). It is easy to check that g∗ restricts to a linear map g∗ : C(G)→ C(H).
A basis B of C(G) is called a cycle basis of G, and its length is `(B) = ∑C∈B |C|.
Among all cycle bases of G, one with smallest possible length is called a minimum cycle
basis, or MCB. It is easy to check that every MCB contains only simple cycles.
The cycle space is a weighted matroid where each element C has weight |C|. Hence
the Greedy Algorithm [10] always terminates with an MCB. (I.e. begin with M = ∅;
then append shortest cycles to it, maintaining independence ofM, until no further shortest
cycles can be appended; then append next-shortest cycles, maintaining independence, until
no further such cycles can be appended; and so on, untilM is a maximal independent set.
ThenM is an MCB.)
Here is our primary criterion for determining if a cycle basis is an MCB.
Proposition 1.1. A cycle basis B = {B1, B2, . . . , Bβ(G)} for a graph G is an MCB if and
only if every C ∈ C(G) is a sum of basis elements whose lengths do not exceed |C|.
Proof. Suppose B is an MCB, but there is a cycle C = ∑β(G)k=1 bkBk (each bk is in F2)
and |C| < |Bk| for some k with bk 6= 0. Then we can exchange basis element Bk for C
and obtain a basis with smaller total length than B, contradicting minimality. Conversely,
suppose B is not an MCB. Assume that the elements B1, B2, . . . are arranged in order of
increasing length. Since the greedy algorithm cannot terminate with basis B, there must be
an element Bp for which the set {B1, B2, . . . , Bp−1} can be extended to an independent
set {B1, B2, . . . , Bp−1, C} with |C| < |Bp|. Necessarily then, C =
∑β(G)
k=1 bkBk with
bi 6= 0, for some p ≤ i ≤ β(G), and |C| < |Bi|.
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 (u, x)(v, y) where uv ∈ E(G)
and xy ∈ E(H). We quickly mention a few standard facts; the reader requiring more
background is referred to [6]. Suppose G and H are connected. Then G×H is connected
if and only if one of G and H has an odd cycle. Otherwise, if G and H are both bipartite
then G × H has exactly two components. As G × H has |V (G)| · |V (H)| vertices and
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 103
2|E(G)| · |E(H)| edges we have β(G×H) = 2|E(G)| · |E(H)| − |V (G)| · |V (H)|+ 1
whenever G and H are connected and one has an odd cycle.
Note that the standard projection maps πG : G × H → G and πH : G × H → H
induce projection operators π∗G : C(G×H)→ C(G) and π∗H : C(G×H)→ C(H).
For any simple cycle Cp, we put V (Cp) = Zp = {0, 1, 2, . . . , p− 1} and we agree that
the edges of Cp join i to i + 1 for each i ∈ Zp. Thus an arbitrary edge is written i(i + 1),
which we take care not to confuse with multiplication.
2 An MCB for G×K2
To motivate our approach for constructing MCB’s ofG×Cq , we now examine the problem
of constructing an MCB for G ×K2, where G is an arbitrary connected graph and K2 is
the complete graph on 2 vertices. We put V (K2) = {0, 1} and denote its edge as 01.
We remark at the onset that an MCB of G typically bears little resemblance to an MCB
ofG×K2. For example, consider Figure 1. The factorG consists of a pentagon that shares
a vertex with a triangle. Obviously, an MCB forG consists of just two cycles, the pentagon
and the triangle. But an MCB of G×K2 consists of two 8-gons (shown solid and dashed)
plus the 6-gon over the triangle. The two 8-gons do not seem in any way related to any
single element of the MCB for G. Our main task in this section is to uncover how an MCB
for G×K2 is related to the structure of the factor G.
G
G×K2K2
Figure 1: An example of G×K2
Our basic approach is to employ not the cycle structure of G, but instead the cycle
structure of the symmetric digraph on G. Any graph G can be identified with a symmetric
digraph
←→
G obtained by replacing each edge xy of G with an arc −→xy directed from x to y
and an arc −→yx directed from y to x. Thus ←→G has vertex set V (←→G ) = V (G) and arc set
E(
←→
G ) = {−→xy,−→yx : xy ∈ E(G)}. We define an anti-cycle to be a sub-digraph of←→G , each
vertex of which has even in-degree and even out-degree. Figure 2 shows an anti-cycle for
the factor G from Figure 1. Let A(←→G ) denote the set of anti-cycles in←→G . In what follows
we describe how A(←→G ) is naturally identified with C(G×K2), and how “minimum anti-
cycle bases” of A(←→G ) correspond to MCB’s of G×K2.
Figure 2: An anti-cycle in G
Let E(←→G ) denote the power set of E(←→G ) endowed with a vector space structure over
104 Ars Math. Contemp. 2 (2009) 101–119
F2. (Addition is symmetric difference, etc.) As usual, to keep the notation under control we
identify elements of E(←→G ) with sub-digraphs of←→G , so, for example, an element {−→xy} ∈
E(←→G ) is written simply as −→xy. With this convention, the set E(←→G ) is a basis for E(←→G ),
which has dimension 2|E(G)|.
Define a linear map π : E(G × K2) → E(
←→
G ) which acts on the basis E(G × K2)
as π((x, 0)(y, 1)) = −→xy. This is a vector space isomorphism because it sends the basis
E(G×K2) of E(G×K2) injectively onto the basis E(
←→
G ) of E(←→G ). A moment’s thought
confirms that π restricts to an isomorphism π : C(G×K2)→ A(
←→
G ).
0
π(A)
A
K2 1
Figure 3: How anti-cycles in G correspond to cycles in G×K2
Let the length |C| of an element C ∈ C(←→G ) be the number of arcs in C. Observe that
|A| = |π(A)| for every A ∈ C(G×K2). Thus π is a length-preserving isomorphism from
C(G×K2) to A(
←→
G ).
In analogy with the definition of an MCB, we define a minimum anti-cycle basis of←→
G to be a basis {B1, B2, . . . , Bβ(G×K2)} for A(
←→
G ) in which the total length
∑ |Bi| has
the smallest possible value. The remarks above show that π gives an exact correspondence
between minimum anti-cycle bases of
←→
G and minimum cycle bases of G×K2. This leads
to the following result linking MCBs of G×K2 to the structure of G.
Proposition 2.1. Let π : C(G × K2) → A(
←→
G ) be the isomorphism defined by the rule
π((x, 0)(y, 1)) = −→xy. Then {B1, B2, B3, . . . , Bβ(G×K2)} is a minimum anti-cycle basis
for
←→
G if and only if the set {π−1(B1), π−1(B2), π−1(B3), . . . , π−1(Bβ(G×K2))} is an
MCB for G×K2.
We do not address the question of how to compute a minimum anti-cycle basis, since
our main goal is to express an MCB of G × K2 in terms of invariants of the factors, and
Proposition 2.1 accomplishes this in the sense that the structure of
←→
G is inherent in the
structure of G. We’ll later see that other cycle structures in
←→
G can be used to construct
MCB’s in G× Cq .
3 The Diamond Space
Our ultimate goal is to obtain MCB’s of G × Cq , where q is odd and one of the factors is
triangle-free. In this situation G × Cq is triangle-free, for if K were a triangle in G × Cq ,
then πG(K) and πCq (K) would be a triangles in G and Cq . Hence the shortest cycles in
G× Cq have length at least four. Since—by the greedy algorithm—an MCB must contain
a maximal independent set of shortest cycles, we are especially concerned with forming
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 105
a maximal independent set of squares. This section deals with certain squares in G × Cq
called diamonds.
If Q = abc and R = def are paths of length 2 in graphs G and H , respectively, let QR
denote the 4-cycle (a, e)(b, f)(c, e)(b, d)(a, e) in G×H , as illustrated in Figure 4. Such a
subgraph QR is called a diamond in G ×H , and the subspace D(G ×H) ⊆ C(G ×H)
spanned by all diamonds is called the diamond space of C(G × H). In what follows we
construct a basis of diamonds for D(G× Cq). Our construction involves certain spaces of
paths of length 2 in the factors. Let us agree to call a path abc of length 2 in a graph a P2
centered at b in the graph. The P2’s of Cq are all of form (i− 1)i(i+ 1) for i ∈ Zq .
Q
R
(a, e)
(b, f)
(c, e)
(b, d)
QR
d
e
f
a b c
Figure 4: A diamond QR
Given a vertex b ∈ V (G), let S(b) be the set of edges of G that are incident with
b. (We may think of S(b) as a subgraph of G, i.e. the “star” at b.) Let P(G, b) =
{X ⊆ E(S(b)) : |X| is even}. Note that P(G, b) is the subspace of E(S(b)) spanned
by the P2’s in G centered at b, so we call it the P2 space of G at b. Observe that
P(G, b) is the kernel of the surjective linear map E(S(b)) → F2 given by X 7→ |X|
(mod 2), so we have dim(P(G, b)) = dim(E(S(b))) − 1 = degG(b) − 1. If the neigh-
borhood of b is labeled as NG(b) = {x0, x1, x2, . . . , xdeg(b)−1}, then the set of P2’s
B = {x0bx1, x0bx2, . . . , x0bxdeg(b)−1} is a basis for P(G, b). A basis for P(G, b) that
consists entirely of P2’s is called a P2 basis for P(G, b). A P2 basis for P(G, b) of the
form B above (for which some edge x0b belongs to every element of the basis) is called a
standard P2 basis with common edge x0b. A version of the next lemma was proved in
[9]. For completeness we include a separate proof here.
Lemma 3.1. Suppose T is a tree with at least two edges, and for each t ∈ V (T ) let Tt be
a P2 basis for P(T, t). Then the set of diamonds D = {Q[(i − 1)i(i + 1)] : Q ∈ Tt, t ∈
V (T ), i ∈ V (Cq)} is linearly independent in C(T × Cq).
Proof. We use induction on |E(T )|. First suppose |E(T )| = 2, so T ∼= P2. Label its
vertices so that T = abc. Then D = {[abc][(i − 1)i(i + 1)] : i ∈ V (Cp)}. Notice that
if i 6= j then diamonds [abc][(i − 1)i(i + 1)] and [abc][(j − 1)j(j + 1)] have no edges in
common, since each edge in [abc][(i− 1)i(i+ 1)] has either (a, i) or (c, i) as an endpoint,
but no edge of [abc][(j − 1)j(j + 1)] has these endpoints. Thus the elements of D are
pairwise edge-disjoint, so D is linearly independent.
Now suppose the statement is true for any tree T with fewer than n ≥ 3 edges, and
suppose |E(T )| = n. For each x ∈ V (T ), let Tx be a P2 basis for P(T, x). Observe
106 Ars Math. Contemp. 2 (2009) 101–119
that there is an edge of T that belongs to exactly one P2 in T =
⋃
x∈V (T ) Tx. To see this,
note that since |Tx| = degT (x) − 1 and the sets Tx are pairwise disjoint, we have |T | =∑
x∈V (T )(degT (x) − 1) = 2|E(T )| − |V (T )| = |E(T )| − 1. Since each element of T
has two edges, then on average each edge of T belongs to 2(|E(T )−1)|E(T )| < 2 elements in T .
Thus some edge of T belongs to fewer than two P2’s in T . But each edge in T belongs to
at least one element of T , so some edge of T belongs to exactly one P2 in T , as claimed.
Notice that if st is an edge that belongs to just one P2 in T , then one of s or t has
degree 1, for otherwise each of Ts and Tt have (distinct) elements that contains st. Thus
there is an st ∈ E(T ), with degT (s) = 1, such that st meets exactly one diamond stu
in T . Let T ′ = T − s. (i.e. T ′ is T with vertex s and edge st removed.) Now, for each
x ∈ V (T ′)− {t} the set Tx remains a P2 basis for P(T ′, x), and Tt − {stu} is a P2 basis
for P(T ′, t). Let T ′x = Tx for x ∈ V (T ′)− {t} and T ′t = Tt − {stu}.
By induction, the set D′ = {Q[(i − 1)i(i + 1) : Q ∈ T ′x, x ∈ V (T ′), i ∈ V (Cq)}
is linearly independent in C(T ′ × Cq) ⊆ C(T × Cq). To complete the proof we need to
show that the set D = {Q[(i − 1)i(i + 1)] : Q ∈ Tx, x ∈ V (T ), i ∈ V (Cq)} is linearly
independent. Notice that D is a disjoint union D = D′ ∪ D′′, where D′′ = {[stu][(i −
1)i(i+1)] : i ∈ V (Cq)}. By induction, the setD′′ is linearly independent in C(stu×Cq) ⊆
C(T ×Cq). To show thatD is independent, it suffices to show that span(D′)∩ span(D′′) =
{0}. Thus suppose W ∈ span(D′) ∩ span(D′′). Notice that D′′ consists of exactly q
diamonds, all of form [stu][(i − 1)i(i + 1)], and no two of which share an edge. Thus
since W ∈ span(D′′), W is the (possibly empty) edge-disjoint union of diamonds from
D′′. But also W ∈ span(D′), so W can’t have any edges of form (s, i)(t, i ± 1). Since
every diamond in D′′ has such edges, we conclude W = 0.
One may wonder if the tree T in Lemma 3.1 can be replaced with an arbitrary connected
graph G. If Gx is a P2 basis for P(G, x) for each x ∈ V (G), will the set of diamonds D =
{Q[(i−1)i(i+1)] : Q ∈ Gx, x ∈ V (G), i ∈ V (Cq)} be linearly independent in C(G×Cq)?
Though the answer is “no,” just a small number of diamonds need to be removed to make
the set independent. The details are outlined in the following construction for a linearly
independent set of diamonds in D(G × Cq). We will only prove independence here, but
later we’ll see that the set is actually a basis for D(G× Cq).
Construction 3.2. (A basis of diamonds for D(G× Cq), with G connected and q odd.)
Let T be a spanning tree of G.
Let E(G)− E(T ) = {b1c1, b2c2, . . . , bβ(G)cβ(G)}.
For each x ∈ V (G) let Gx be a standard P2 basis forP(G, x) whose common edge belongs
to T .
For each 1 ≤ i ≤ β(G) let aibici denote the element of Gbi containing the edge bici.
Let D = {Q[(i− 1)i(i+ 1)] : Q ∈ Gx, x ∈ V (G), i ∈ V (Cq)} − {[aibici][012] : 1 ≤ i ≤
β(G)}.
ThenD is a linearly independent set of diamonds. Moreover, |D| = β(G×Cq)−β(G)−1.
Proof. We use induction on β(G). If β(G) = 0, then G = T . In this case D is linearly
independent by Lemma 3.1.
Now assume the statement is true for all G with β(G) < n, for some integer n ≥ 1.
Let G be a graph with β(G) = n, and let T and D be as stated in the construction. Also,
for each 1 ≤ i ≤ β(G), let bicidi denote the element of Gci containing the edge bici.
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 107
LetG′ = G−bβ(G)cβ(G), so β(G′) = n−1, and T is a spanning tree forG′. For brevity,
put k = β(G) = β(G′) + 1. Notice that if x ∈ V (G) − {bk, ck}, then Gx is a standard
P2 basis (with common edge in T ) for both P(G, x) and P(G′, x) because P(G, x) =
P(G′, x). Also Gbk − {akbkck} is a standard P2 basis for P(G′, bk) with common edge
in T . (Reason: Gbk is a standard P2 basis for P(G, bk) with common edge akbk in T , so
akbkck is the only element of Gbk that contains the edge bkck. All other members of Gbk are
P2’s inG′. Since dim(P(G′, bk)) = degG′(bk)−1 = degG(bk)−2 = dim(P(G, bk))−1,
it follows that removing the single path akbkck from Gbk must leave a basis for P(G′, bk).)
For the same reason Gck − {bkckdk} is a standard P2 basis for P(G′, ck) with common
edge in T . Put G′x = Gx if x ∈ V (G) − {bk, ck}, and G′bk = Gbk − {akbkck}, and G′ck =
Gck − {bkckdk}. Then for each x ∈ V (G′), the set G′x is a standard P2 basis for P(G′, x)
with common edge in T .
Observe that G′ meets the conditions for Construction 3.2 because T is a spanning tree
of G′, and E(G′)−E(T ) = {b1c1, b2c2, . . . , bβ(G′)cβ(G′)}, and for each x ∈ V (G′) the
set G′x is a standard P2 basis for P(G′, x) whose common edge belongs to T , and for each
1 ≤ i ≤ β(G′), the path aibici is the element of G′bi containing bici. By induction, the set
D′ = {Q[(i − 1)i(i + 1)] : Q ∈ G′x, x ∈ V (G′), i ∈ V (Cq)} − {[aibici][012] : 1 ≤ i ≤
k − 1} is linearly independent.
Now, D is a disjoint union D = D′ ∪ D′′ where D′′ = {Q[(i − 1)i(i + 1)] : Q ∈
{akbkck, bkckdk}, i ∈ V (Cq)} − { [akbkck][012] } is a subset of the diamonds in the
subgraph [akbkckdk] × Cq . To show that D is linearly independent, we just need to show
that D′′ is linearly independent and span(D′) ∩ span(D′′) = {0}. This is perhaps most
easily explained graphically. (Note: we cannot necessarily apply Lemma 3.1 here, for it
is possible ak = dk, in which case akbkckdk is not a tree.) Figure 5 shows the diamonds
in D′′ for the case q = 9, and the picture for the general case (with q odd) is similar.
Diamonds [akbkck][(i − 1)i(i + 1)] and [bkckdk][(i − 1)i(i + 1)] from D′′ are petals in
a flower-like arrangement, with the diamond [akbkck][012] missing (it does not belong to
D′′). The shaded region covers the edges of form (bk, i)(ck, i ± 1) which form the set
E(G× Cq)− E(G′ × Cq).
The setD′′ is linearly independent as follows. Suppose a sum of diamonds inD′′ equals
zero. Then the diamond labeled X cannot occur in the sum, because the sum contains no
diamond that can cancel the edge (ck, 1)(bk, 2) of X . Consequently the diamond labeled
Y cannot occur in the sum because the sum has no term to cancel the edge (bk, 2)(ck, 3)
of Y . Similarly, the diamond Z cannot occur in the sum because the sum has no term to
cancel the edge (ck, 3)(bk, 4). Continuing around the flower in this pattern we see that the
sum has no nonzero terms, so D′′ is linearly independent.
Next we show span(D′) ∩ span(D′′) = {0}. Suppose W ∈ span(D′) ∩ span(D′′).
Now, the diamonds in D′ are subgraphs of E(G′ × Cq), so none of them have edges in
E(G × Cq) − E(G′ × Cq) (shaded in the figure). Thus W has no edges of this form. At
the same time, since W is in span(D′′) it must be a sum of diamonds in D′′. Then the
diamond X cannot be in the sum because the sum contains no diamond that can cancel the
edge (ck, 1)(bk, 2) of X . Repeating the argument in the previous paragraph, the sum has
no nonzero terms, so W = 0.
This completes the proof that D is linearly independent. To prove the statement about
108 Ars Math. Contemp. 2 (2009) 101–119
(d
k
,0)
(d
k ,2)
(dk,4)
(d
k
,6
)
(d
k
,8
)
(d
k ,1)
(dk ,3)
(dk
,5)
(d
k
,7
)
(b
k
,0)
(b
k ,2)
(bk,4)
(b k
,6
)
(b
k
,8
)
(b
k ,1)
(bk ,3)
(bk
,5)
(b
k
,7
)(ck ,1)
(ck ,3)
(ck
,5)
(c
k
,7
) (ck
,0)
(c
k ,2)
(ck,4)
(c k
,6
)
(c
k
,8
)
(a
k ,1)
(ak ,3)
(ak
,5)
(a
k
,7
) (a
k
,0)
(a
k ,2)
(ak,4)
(a
k
,6
)
(a
k
,8
)
Y
X
Z
Figure 5: The set D′′
the cardinality, note that the definition of D yields
|D| =
∣∣{Q[(i− 1)i(i+ 1)] : Q ∈ Gx, x ∈ V (G), i ∈ V (Cq)}
∣∣−∣∣{[aibici][012] : 1 ≤ i ≤ β(G)}
∣∣
=
∑
x∈V (G)
|Gx|q − β(G)
= q

 ∑
x∈V (G)
degG(x)− 1

− (|E(G)| − |V (G)|+ 1)
= q(2|E(G)| − |V (G)|)− (|E(G)| − |V (G)|+ 1)
= (2|E(G)|q − |V (G)|q + 1)− (|E(G)| − |V (G)|+ 1)− 1
= β(G× Cq)− β(G)− 1.
The proof is now complete.
Before moving on, we visit a consequence of Construction 3.2 that will be useful.
Lemma 3.3. Suppose G is a connected non-bipartite graph, e is an edge of Cq and P is
the path Cq − e. Let ab ∈ E(P ), and regard G× ab ∼= G×K2 as a subgraph of G× P .
Then C(G×P ) = C(G×ab)⊕D(G×P ). Moreover, if C = A+B with A ∈ C(G×ab)
and B ∈ D(G× P ), then |C| ≥ |A|.
Proof. Let the partite sets of P be Xa and Xb, with a ∈ Xa and b ∈ Xb. Observe that
there is a homomorphism ρ : G × P → G × ab defined as ρ(x, i) = (x, a) if i ∈ Xa
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 109
and ρ(x, i) = (x, b) if i ∈ Xb. Note that ρ is the identity on G × ab, and it thus induces a
projection ρ∗ : C(G × P ) → C(G × ab). Therefore C(G × P ) = C(G × ab)⊕ ker(ρ∗),
so dim(ker(ρ∗)) = β(G × P ) − β(G × ab). Now ρ∗(D) = 0 for any diamond D, so
D(G× P ) ⊆ ker(ρ∗). We will finish the proof by producing a linearly independent set of
diamonds in D(G× P ) of cardinality β(G× P )− β(G× ab).
We can create an independent set of diamonds in D(G× P ) by removing from the set
D of Construction 3.2 all diamonds that are not in G× P . If e = c(c+ 1), we remove the
diamonds of form Q[(c − 1)c(c + 1)] and Q[c(c + 1)(c + 2)] and obtain the independent
set B = {Q[(i − 1)i(i + 1)] : Q ∈ Gx, x ∈ V (G), i ∈ Zq − {c, c + 1}} of diamonds in
G× P . Observe
|B| =
∑
x∈V (G)
|Gx|(q − 2) = (q − 2)
∑
x∈V (G)
(degG(x)− 1)
= (q − 2)(2|E(G)| − |V (G)|)
=
(
2|E(G)|(q − 1)− V (G)|q + 1
)
−
(
2|E(G)| − 2|V (G)|+ 1
)
= β(G× P )− β(G× ab).
Finally, suppose C = A + B as in the statement of the lemma. Now, |C| ≥ |ρ∗(C)|
because any edge in ρ∗(C) must be the image under ρ∗ of at least one edge in C. Since
ρ∗(C) = ρ∗(A+B) = ρ∗(A) + ρ∗(B) = ρ∗(A) = A, we have |C| ≥ |A|.
4 The Product of Two Odd Cycles
In this section we take up the problem of finding an MCB for the product of cycles Cp×Cq
where p and q are odd and at least one is greater than 3. For simplicity assume p ≤ q. This
is a special case of our ultimate problem of finding an MCB of G × Cq , but treating it
now will help us understand some of the subtleties of the general problem and put us in
a position to better understand and motivate our general construction. The discussion is
informal and is intended for illumination only, and any lack of rigor will be compensated
in the subsequent section. Though the arguments used in this section are topological, those
that follow will be entirely combinatorial.
Observe that Cp × Cq can be embedded on the torus with pq square regions whose
boundaries are the diamonds of Cp×Cq . This is illustrated for C5×C9 in Figure 6(a) and
for C5 × C11 in Figure 6(b). In each case the torus is an identification space obtained by
identifying paths A (of length p), paths B (of length p), and the zig-zag path C (of length
q − p). The general case is illustrated in figures 7(a) and 7(b).
The set of all pq diamonds is linearly dependent, for if they are all added together their
edges will cancel pair-by-pair. But set D of Construction 3.2 is independent and |D| =
β(Cp×Cq)− β(Cq)− 1 = (2pq− pq+ 1)− 1− 1 = pq− 1. Thus D contains all but one
diamond, and the missing one is the sum everything in D, so D is a basis for D(Cp ×Cq).
Let’s now use the Greedy Algorithm to obtain an MCB. There are no cycles of length
less than 4, so begin by settingM := D. Since β(Cp × Cq) = pq + 1 = |M| + 2, there
are just two more cycles to append.
As an aid in finding these two cycles, we claim any even cycle Z ∈ C(Cp × Cq) with
|Z| < 2p is a sum of diamonds, and is thus already in span(M). For if Z is such an
even cycle, the homomorphism π∗Cp : C(Cp × Cq) → C(Cp) = {0, Cp} must send Z to
an even cycle, so π∗Cp(Z) = 0. Then for any edge e = ab ∈ E(Cp), cycle Z must have
110 Ars Math. Contemp. 2 (2009) 101–119
Ars Mathematica Contemporanea x (xxxx) 1–x 9
of the subtleties of the general problem and put us in a position to better understand and motivate our
general construction. The discussion is informal and is intended for illumination only, and any lack
of rigor will be compensated in the subsequent section. Though the arguments used in this section
are topological, those that follow will be entirely combinatorial.
Observe that Cp × Cq can be embedded on the torus with pq square regions whose boundaries
are the diamonds ofCp×Cq . This is illustrated forC5×C9 in Figure 6(a) and forC5×C11 in Figure
6(b). In each case the torus is an identification space obtained by identifying paths A (of length p),
paths B (of length p), and the zig-zag path C (of length q − p). The general case is illustrated in
figures 7(a) and 7(b).
00 11 22 33 44 05
07 18 20 31 42 03 14
05 16 27 38 40 01 12 23
14 25 36 47 08 10 21 32
23 34 45 06 17 28 30 41
32 43 04 15 26 37 48 00
41 02 13 24 35 46 07 18
00 11 22 33 44 05 16
 A -
 A -
?
B
6
?
B
6
C
C
00 11 22 33 44 05
09 1 10 20 31 42 03 14
07 18 29 3 10 40 01 12 23
05 16 27 38 49 0 10 10 21 32
14 25 36 47 08 19 2 10 30 41
23 34 45 06 17 28 39 4 10 00
32 43 04 15 26 37 48 09 4 10
41 02 13 24 35 46 07 18
00 11 22 33 44 05 16
 A -
 A -
?
B
6
?
B
6
C
C
C5 × C9 C5 × C11
(a) (b)
Figure 6: The graph Cp × Cq on the torus
The set of all pq diamonds is linearly dependent, for if they are all added together their edges will
cancel pair-by-pair. But set D of Construction 4 is independent and |D| = β(Cp×Cq)− β(Cq)− 1
= (2pq − pq + 1)− 1− 1 = pq − 1. Thus D contains all but one diamond, and the missing one is
the sum everything in D, so D is a basis for D(Cp × Cq).
Let’s now use the Greedy Algorithm to obtain an MCB. There are no cycles of length less than
4, so begin by settingM := D. Since β(Cp × Cq) = pq + 1 = |M| + 2, there are just two more
cycles to append.
As an aid in finding these two cycles, we claim any even cycleZ ∈ C(Cp×Cq) with |Z| < 2p is a
sum of diamonds, and is thus already in span(M). For ifZ is such an even cycle, the homomorphism
π∗Cp : C(Cp × Cq) → C(Cp) = {0, Cp} must send Z to an even cycle, so π∗Cp(Z) = 0. Then for
any edge e = ab ∈ E(Cp), cycle Z must have an even number me of edges of form (a, x)(b, y) for
which πCp((a, x)(b, y)) = ab. Since 2p > |Z| =
∑
e∈E(Cp)me, it follows that me = 0 for some
e ∈ E(Cp). Hence Z is a cycle in the graph (Cp − e) × Cq . By applying the same argument to
the factor Cq (and using p ≤ q) we see Cq must have some edge f for which Z is a cycle in the
product (Cp − e) × (Cq − f) of paths. A product of paths has two planar components which can
be embedded in the plane so that the boundaries of all interior regions are diamonds. By MacLane’s
theorem, these diamonds span the cycle space, so Z is a sum of diamonds.
C5 × C9 C5 C11
(a) (b)
Figure 6: The graph Cp × Cq on the torus
an even number me of edges of form (a, x)(b, y) for which πCp((a, x)(b, y)) = ab. Since
2p > |Z| = ∑e∈E(Cp)me, it follows that me = 0 for some e ∈ E(Cp). Hence Z is a
cycle in the grap (Cp − e) × Cq . By applyi g the same argum nt to the factor Cq (and
using p ≤ q) we see Cq must have some edge f for which Z is a cycl in the product
(Cp − e) × (Cq − f) of paths. A product of paths has two planar components which can
be embed ed i the plan so that the boundaries of all interior regions are diamonds. By
MacLane’s theorem, these diamonds span the cycle space, so Z is a sum of diamonds.
In Figure 6 the edges of the products are colored solid and dashed according to whether
they run horizontally or vertically in the grids. With this coloring, every diamond has two
edges of each color, so any element of span(M) has an even number of edg s of each
color. Now the even cycle A + B of length 2p has p (odd) edges of each color, A + B /∈
span(M). Further, A+C and B+C are cycles of length q (odd), so they are certainly not
in span(M). Since A+B = (A+C) + (B+C), it follows that appending toM any two
elements of {A+B,A+ C,B + C} will produce a basis.
Now continue with the Greedy Algorithm. We know that if an even cycle is appended
toM, the even cycle must have length no less than 2p. At the same time, since Cp × Cq
has odd cycles, at least one odd cycle must appear in an MCB, and such an odd cycle can
have length no less than q. Therefore if q < 2p, thenM can be extended to an MCB by
appending to it the odd cycles A+C and B+C of length q. On the other hand, if 2p < q,
thenM is extended to an MCB by appending to it the even cycle A + B of length 2p the
odd cycle A+ C of length q. This proves the following result.
Proposition 4.1. Suppose p and q are odd integers, p ≤ q and max{p, q} > 3.
If q < 2p, then Cp × Cq has an MCB consisting of pq − 1 squares and two q-cycles.
If 2p < q, then Cp×Cq has an MCB consisting of pq−1 squares, a 2p-cycle and a q-cycle.
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 111
10 Ars Mathematica Contemporanea x (xxxx) 1–x
 -
?
6
?
6
?
6
A
A
B
B
C
C
p
p
1
2 (q − p)
1
2 (q − p)0p
0p
0p
00
00
00 A
A
B
B
C
00
0p
(a) (b)
Figure 7: The graph Cp × Cq on the torus
In Figure 6 the edges of the products are colored solid and dashed according to whether they run
horizontally or vertically in the grids. With this coloring, every diamond has two edges of each color,
so any element of span(M) has an even number of edges of each color. Now the even cycle A+B
of length 2p has p (odd) edges of each color, A + B /∈ span(M). Further, A + C and B + C are
cycles of length q (odd), so they are certainly not in span(M). Since A+B = (A+C) + (B+C),
it follows that appending toM any two elements of {A+B,A+ C,B + C} will produce a basis.
Now continue with the Greedy Algorithm. We know that if an even cycle is appended toM, the
even cycle must have length no less than 2p. At the same time, since Cp × Cq has odd cycles, at
least one odd cycle must appear in an MCB, and such an odd cycle can have length no less than q.
Therefore if q < 2p, thenM can be extended to an MCB by appending to it the odd cycles A + C
and B + C of length q. On the other hand, if 2p < q, thenM is extended to an MCB by appending
to it the even cycle A+ B of length 2p the odd cycle A+ C of length q. This proves the following
result.
Proposition 6. Suppose p and q are odd integers, p ≤ q and max{p, q} > 3.
If q < 2p, then Cp × Cq has an MCB consisting of pq − 1 squares and two q-cycles.
If 2p < q, then Cp × Cq has an MCB consisting of pq − 1 squares, a 2p-cycle and a q-cycle.
Figures 6(a) and 6(b) illustrate this proposition. In Figure 6(a) C5 × C9 has an MCB consisting
of 44 diamonds, and two 9-cyclesA+C andB+C. In Figure 6(a) C5×C11 has an MCB consisting
of 54 diamonds, one 10-cycle A+B and one 11-cycle A+ C.
5 An MCB for G× Cq
In the previous section we constructed an MCB for Cp × Cq where p, q are odd, p ≤ q and
max{p, q} > 3. We now generalize this by replacing the factor Cp with a connected graph G
whose shortest odd cycle has length p. That is, we construct an MCB for G × Cq where p ≤ q and
max{p, q} > 3. Under these hypotheses every odd cycle in G×Cq has length at least q, so G×Cq
is triangle-free.
(a) (b)
Figure 7: The graph Cp × Cq on the torus
Figures 6(a) and 6(b) illustrate this propositi n. In Figure 6(a) C5 × C9 has an MCB
consisting of 44 diamonds, and two 9-cycles A + C and B + C. In Figure 6(a) C5 × C11
has an MCB consisting of 54 diamonds, one 10-cycle A+B and one 11-cycle A+ C.
5 An MCB for G× Cq
In the previous section we constructed an MCB for Cp ×Cq where p, q are odd, p ≤ q and
max{p, q} > 3. We now generalize this by replacing the factor Cp with a connected graph
G whose shortest odd cycle has length p. That is, we construct an MCB for G×Cq where
p ≤ q and max{p, q} > 3. Under these hypotheses every odd cycle in G × Cq has length
at least q, so G× Cq is triangle-free.
As was the case for G × K2 in Section 2, we should not expect an MCB of G × Cq
to correspond in any way to an MCB of G. And as in Section 2 our approach here will
be to replace G with its symmetric digraph
←→
G and transfer minimal cycle structures of
←→
G
to G × Cq . However, since G × Cq has odd cycles (unlike G ×K2), the anti-cycle space
A(←→G ) (whose elements all possess an even number of arcs) does not have an adequate
cycle structure for the job at hand, and we will have to enlarge it slightly. The releva t
definitions f llow.
As in Section 2, let
←→
G denote the symmetric digraph on G with arc set E(
←→
G ) =
{−→xy,−→yx : xy ∈ E(G)}. A pair {−→xy,−→yx} is called a double edge of←→G . A sub-digraph of←→
G is symmetric if whenever −→xy is one of its arcs, then −→yx is also one of its arcs (i.e. if
every one of its arcs is part of a double edge.)
Let C(←→G ) be the kernel of the linear map λ : E(←→G ) → V(G) defined as λ(−→xy) =
{x} + {y}. One easily checks that C(←→G ) consists of the edge sets of the sub-digraphs
of
←→
G for which at each vertex the sum of the in- and out-degree is even. Observe that
A(←→G ) is a proper subspace of C(←→G ), provided that G has at least one edge. Indeed,
any double edge {−→xy,−→yx} ∈ E(←→G ) is in C(←→G ) but not in A(←→G ). The range of λ is
112 Ars Math. Contemp. 2 (2009) 101–119
the subspace of {X ⊂ V (G) : |X| is even} of V(G), and its dimension is |V (G)| − 1.
(Because it is the kernel of the surjective linear map V(G) → F2 defined as X → |X|
(mod 2).) Therefore, since rank(λ) + dim(ker(λ)) = dim(E(←→G )) = 2|E(G)|, we see
dim(C(←→G )) = 2|E(G)| − |V (G)|+ 1.
Just as we regard elements of C(G) as (eulerian) subgraphs of G, we regard elements
of C(←→G ) as the sub-digraphs of←→G for which the total degree (in-degree plus out-degree)
of each vertex is even. Recall that an orientation of a graph is an assignment of a direction
to each of its edges. Thus if A ∈ C(G), any orientation of A is in C(←→G ). However an
orientation of A has no double edges, while an element of C(←→G ) may have double edges.
Consequently though C(←→G ) contains all the orientations of eulerian subgraphs of G, not
every element of C(←→G ) is such an orientation.
We now define a projection π : C(G × Cq) → C(
←→
G ). Consider the linear map π :
E(G× Cq)→ E(
←→
G ) which acts on the basis E(G× Cq) as
π((v, i)(w, j)) =
{ −→vw if j = i+ 1−→wv if j = i− 1.
It is straightforward to check that this restricts to a linear map π : C(G× Cq)→ C(
←→
G ).
π(D)
D
i− 1
i
i+ 1
Figure 8: Projection of a diamond
As an example, observe that (as illustrated in Figure 8) if D is a diamond, then π(D)
consists of two double edges. It follows that if Y ∈ D(G× Cq), then π(Y ) consists of an
even number of double edges.
Our reason for constructing C(←→G ) is to have a richer version of C(G) so that, roughly,
we may ultimately be able to lift some minimal cycle structure in C(←→G ) to C(G × Cq).
We’ve seen that if Y ∈ D(G × Cq), then π(Y ) is a symmetric sub-digraph of
←→
G that
consists of an even number of double edges. By Construction 3.2 we already have a set D
of diamonds that spans D(G×Cq), so we are not interested in lifting such sub-digraphs Y
to cycles in D(G×Cq). Thus we next cut down the size of C(
←→
G ) by forming the quotient
of if with the space of symmetric digraphs with an even number of double edges.
Let V = {Y ∈ C(←→G ) : Y is symmetric and |Y | ≡ 0 (mod 4)}. Note V is precisely the
subset of C(←→G ) whose elements are symmetric digraphs with an even number of double
edges. (Each double edge contains two opposing arcs, so an even number of double edges
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 113
yields a total number of arcs that is a multiple of 4.) Clearly V is a subspace of C(←→G ). If
we identify the double edges in
←→
G with edges in G, then V is identified with the subspace
W = {X ⊆ E(G) : |X| is even } of E(G). Since dim(W) = |E(G)| − 1, we obtain
dim(V) = |E(G)| − 1.
Now consider the quotient C(←→G )/V . The dimension of this space is dim(C(←→G )) −
dim(V) = (2|E(G)| − |V (G)| + 1) − (|E(G)| − 1) = β(G) + 1. Since its dimension is
just one more than the dimension of C(G), we would expect the structure of C(←→G )/V to
be similar to — but slightly richer than — the structure of C(G). In fact we will soon see
that elements of C(←→G )/V can be lifted to part of an MCB for G× Cq , whereas that is not
necessarily possible for lifts of elements of C(G).
Example 5.1. As a specific example of C(←→G )/V , consider the case G = Cp, where p is
odd. Note that C(←→G )/V has dimension β(G)+1 = 2. LetA1 be the digraph obtained from
Cp by giving it the orientation where each arc is directed from i to i+1. LetA2 beA1 with
arcs reversed, that is the arcs in A2 are directed from i to i − 1. Since neither A1 nor A2
is symmetric, A1 + V and A2 + V are nonzero in C(
←→
G )/V . Also A1 +A2 is a symmetric
digraph with p (odd) double edges, soA1 +A2 /∈ V It follows that the set {A1+V, A2+V}
is linearly independent in C(←→G )/V . Thus C(←→G )/V = {V, A1+V, A2+V, (A1+A2)+V}.
Definition 5.2. Let
−→
C n be the digraph with vertices Zn and with arcs directed from i to
i+ 1 for each i ∈ Zn. A sub-digraph C in
←→
G is called a directed cycle if it is isomorphic
to
−→
C n.
In the next lemma we need the linear function f : E(←→G ) → E(G) defined on basis
E(
←→
G ) as f(−→xy) = xy. Thus f simply eliminates all double edges of its argument and
“forgets” the orientation of the remaining arcs. The kernel of f is the space of symmetric
digraphs in E(←→G ). It is easy to check that f restricts to a map f : C(←→G )→ C(G).
Lemma 5.3. If G is non-bipartite, then C(←→G )/V is spanned by the elements A+ V where
A is a directed odd cycle or an anti-cycle.
Proof. Let A = {A1, A2, . . . , Aβ(G)} be a basis of C(G) consisting of simple cycles (an
MCB will suffice). For each index i, give Ai an orientation that makes it an anti-cycle
if |Ai| is even, or a directed cycle if |Ai| is odd. Call the resulting digraph A′i. Thus
we have f(A′i) = Ai. The set A′ = {A′1 +V, A′2 +V, . . . , A′β(G) +V} is linearly in-
dependent in C(←→G )/V for the following reason. Suppose ∑i∈I(A′i +V) = V , where
I ⊆ {1, 2, . . . , β(G)}. Then ∑i∈I A′i ∈ V . Since any element of V is symmetric we have
f
(∑
i∈I A
′
i
)
=
∑
i∈I Ai = 0. Thus I = ∅, showing A′ is independent.
Now let A′β(G)+1 be the symmetric digraph on a simple odd cycle of G. (That is
it is obtained by replacing each edge of a simple odd cycle of G with a double edge.)
Then A′β(G)+1 is an anti-cycle. Now even though A
′
β(G)+1 is symmetric, it has an odd
number of double edges so A′β(G)+1 +V is nonzero in C(
←→
G )/V . We now show that it is
not a linear combination of elements in A′. Suppose to the contrary that A′β(G)+1 +V =∑
i∈I(A
′
i+V). Then A′β(G)+1+V =
(∑
i∈I A
′
i
)
+V , so∑i∈I A′i is symmetric, as it is the
114 Ars Math. Contemp. 2 (2009) 101–119
sum of the symmetric digraph A′β(G)+1 and a symmetric graph in V . Applying f we have∑
i∈I Ai = 0, a contradiction.
Thus we have linearly independent set {A′1+V, A′2+V, . . . , A′β(G)+V, A′β(G)+1+V}
with each A′i is an anticycle or a directed odd cycle. Since C(
←→
G )/V is known to have
dimension β(G) + 1, we are done.
If à ∈ C(G × Cq) and π(Ã) = A, then certainly |Ã| ≥ |A| because each arc in A
is the projection of at least one edge in Ã. Moreover |A| is odd if and only if |Ã| is odd,
and in such cases |Ã| ≥ max{q, |A|} because G × Cq has no odd cycles of length less
than q. The next lemmas show that if A is an anti-cycle or a directed odd cycle, then there
is some à ∈ C(G × Cq) for which π(Ã) = A (modulo V), and for which à attains the
minimum length |A| if A is an anti-cycle, or max{q, |A|} if A is a directed odd cycle. Let
π′ : C(G× Cq)→ C(
←→
G )/V be the map π′(C) = π(C)+V .
Lemma 5.4. If A is an anti-cycle in C(←→G ), then there is a cycle à ∈ C(G × Cq) with
|Ã| = |A| and π(Ã) = A. In particular π′(Ã) = A+V .
Proof. Given anti-cycle A, let à = {(x, 0)(y, 1) : −→xy ∈ E(A)}, as illustrated in Figure 3.
By construction |Ã| = |A| and π(Ã) = A.
Lemma 5.5. If A is a directed odd cycle in C(←→G ), then there is a cycle à ∈ C(G × Cq)
with |Ã| = max{q, |A|} and π′(Ã) = A+V .
Proof. Say A has n vertices. Label its vertices with the elements of Zn so that each arc of
A has form
−−−−→
i(i+ 1). We consider four cases.
Case (a). Suppose q > n and q − n ≡ 0 (mod 4). Let à be the concatenation of paths
L = (0, 0)(1, 1)(2, 2) . . . (n− 1, n− 1)(0, n)
and M = (0, n)(1, n+ 1)(0, n+ 2)(1, n+ 3) . . . (0, 0)
of lengths n and q−n respectively, which are shown solid and dashed in Figure 9(a). Then
|Ã| = q = max{q, |A|}. Further, π(L) = A. Moreover, π sends every two successive
edges of M to
−→
01 +
−→
10. Since the length of M is a multiple of 4, it follows that π(M) = 0.
Therefore π(Ã) = π(L) + π(M) = A+ 0 = A, so π′(Ã) = A+V , as required.
Case (b). Suppose q > n and q − n ≡ 2 (mod 4). If we used L and M from the
previous case, then π(L) =
−→
01 +
−→
10, so π(Ã) would be A with the arc 01 replaced with 10.
Instead, let à be the concatenation of
L = (0, 0)(n− 1, 1)(n− 2, 2) . . . (1, n− 1)(0, n)
and M = (0, n)(1, n+ 1)(0, n+ 2)(1, n+ 3) . . . (0, 0)
which are shown solid and dashed, respectively in Figure 9(b). Then π(L) is the reverse
orientation of A, so π(L) + A is a symmetric graph with n (odd) double edges. Also
π(M) =
−→
01 +
−→
10, so π(L) + π(M) + A = π(Ã) + A is a symmetric graph with n − 1
(even) double edges. Hence π(Ã) +A ∈ V , so π′(Ã) = A+V , as required.
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 115
Case (c). Suppose q ≤ n and n− q ≡ 0 (mod 4). Let à be the concatenation of paths
L = (0, 0)(1, 1)(2, 2)(3, 3) . . . (q, 0)
and M = (q, 0)(q + 1, 1)(q + 2, 0)(q + 3, 1)(q + 4, 0) . . . (n− 1, 1)(0, 0)
of lengths q and n − q, which are shown solid and dashed, respectively in Figure 9(c).
Notice that |Ã| = |A| = max{q, |A|}. Also π(Ã) = π(L) + π(M) is the directed graph
obtained fromA by reversing every other arc in the directed path q(q+1)(q+2) . . . 0 inA.
Since the number of arcs in this path is a multiple of 4, π(Ã) is just A with an even number
of arcs reversed. It follows that π(Ã) + A is a symmetric graph with an even number of
double edges, so π(Ã) +A ∈ V , hence π′(Ã) = A+V .
Case (d). Suppose q ≤ n and n− q ≡ 2 (mod 4). Let à be the concatenation of paths
L = (0, 0)(n− 1, 1)(n− 2, 2)(n− 3, 3) . . . (n− q, 0) and
M = (n− q, 0)(n− q + 1, 1)(n− q + 2, 0)(q + 3, 1)(n− q + 4, 0) . . . (n− 1, 1)(0, 0)
of lengths q and n− q and reason as above.
0
1
2
3
4
5
6
7
8
Cq
A A A
(a) (b) (c)
0 1 2 3 4 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12
à à Ã
Figure 9: Lifts of directed odd cycles
In order to lift a minimum cycle structure of C(←→G )/V to part of an MCB of G× Cq it
will be necessary to weight elements A+V not by |A|, but by the number of edges in a lift
of A. Hence the following definition, motivated by the previous two lemmas.
Definition 5.6. If A ∈ C(←→G ) is an anti-cycle or a directed odd cycle then its q-weight is
the integer
wq(A) =
{
|A| if A is an anti-cycle
max{q, |A|} if A is a directed odd cycle.
A basis A = {A1 +V, A2 +V, . . . , Aβ(G)+1 +V} for C(
←→
G )/V is called a minimum
q-weight basis if each Ai is an anti-cycle or a directed odd cycle and the total q-weight
116 Ars Math. Contemp. 2 (2009) 101–119
∑β(G)+1
i=1 wq(Ai) has the minimum possible value among all such bases. (A minimum
q-weight basis exists by Lemma 5.3.)
We can finally state our construction for an MCB of G× Cq .
Construction 5.7. (An MCB for G×Cq where G is connected and non-bipartite, q is odd,
the shortest odd cycle in G has length p ≤ q, and max{p, q} > 3.)
1. Let D be the set of diamonds from Construction 3.2.
2. Let A = {A1 +V, A2 +V, . . . , Aβ(G)+1 +V} be a minimum q-weight basis for
C(←→G )/V .
3. Let à = {Ã1, Ã2, . . . , Ãβ(G)+1} ⊆ C(G×Cq) be such that π(Ãi)+V = Ai+V and
|Ãi| = wq(Ai) for each index 1 ≤ i ≤ β(G) + 1. (As in Lemmas 5.4 and 5.5.)
Then B = Ã ∪ D is an MCB for G× Cq .
Before proving this, let’s look at a simple example.
Example 5.8. Consider the case of constructing an MCB ofG×Cq whereG = Cp, which
was addressed in Section 4. Assume, as we did in that section, that p ≤ q and max{p, q} >
3. In Step 1 of Construction 5.7 the set D is formed, and it has β(Cp×Cq)−β(Cp)− 1 =
pq − 1 diamonds.
Now we move on to Step 2. We computed C(←→G )/V in Example 5.1. Recall that
C(←→G )/V = {V, A1+V, A2+V, A3+V}. where A1 and A2 are opposite orientations on
Cp, and A3 = A1 + A2 is an anti-cycle of length 2p. Note that wq(A1) = wq(A2) = q,
and wq(A3) = 2p. Depending on whether q < 2p or 2p < q, we would choose as our
minimum q-weight basis either A = {A1 +V, A2 +V} or A = {A1 +V, A3 +V}. In
the first case, à = {Ã1, Ã2} consists of two q-cycles. In the second case à = {Ã1, Ã3}
consists of one q-cycle and one 2p-cycle. Notice that the resulting MCB Ã∪D agrees with
Proposition 4.1.
Now we prove that our construction is valid.
Proof. First we confirm that B is a basis of C(G × Cq). Note that |B| = |Ã ∪ D| =(
β(G) + 1
)
+
(
β(G× Cq)− β(G)− 1
)
= β(G× Cq), so we just need to show that B is
independent. Index D as D = {Dd : 1 ≤ d ≤ β(G× Cq)− β(G)− 1} and suppose
∑
i∈I
Ãi +
∑
d∈∆
Dd = 0, (5.1)
where I ⊆ {1, 2, . . . , β(G) + 1} and ∆ is a subset of the set that idexes D. We want to
show I = ∆ = ∅. Taking π′ of both sides of Equation (5.1) produces ∑i∈I π′(Ãi) = V ,
which by choice of the Ãi becomes
∑
i∈I(Ai+V) = V , so I = ∅. Thus
∑
d∈∆Dd = 0 by
Equation (5.1), but since D is linearly independent by construction we have ∆ = ∅. Thus
B is a basis.
To prove that B is minimal, consider any C ∈ C(G× Cq) and put
C =
∑
i∈I
Ãi +
∑
d∈∆
Dd. (5.2)
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 117
According to Proposition 1.1, we just need to show that |C| is not smaller than the length
of any term in this sum. Certainly |C| ≥ |Dd| = 4 for each d ∈ ∆ because the condition
max{p, q} > 3 implies that G×Cq has no triangles, and hence no cycles of length smaller
than 4. We just need to confirm |C| ≥ |Ãi| for each i ∈ I . We will do this in cases.
Case 1. Suppose |C| ≥ q. Take π′ of both sides of (5.2) to obtain
π(C)+V =
∑
i∈I
(Ai+V). (5.3)
Let S be the maximum symmetric sub-digraph of π(C). (So S = 0 if π(C) has no double
edges.) Then π(C) = Y + S where Y consists of all the arcs of π(C) that are not arcs of
S. (So Y = 0 if π(C) is symmetric.) Thus Y has no double edges, so it is an orientation of
the eulerian subgraph f(Y ) ofG. (Recall that f is the function that “erases” the orientation
of Y .) Now, f(Y ) decomposes into a disjoint union of simple cycles, so Y =
∑n
j=1Bj
where the Bj are orientations on pairwise disjoint simple cycles of G. For each index j, let
B′j be an orientation on f(Bj) such that B
′
j is a simple directed odd cycle if |Bj | is odd, or
an anti-cycle if |Bj | is even. ThenBj+B′j is symmetric for each j, so S+
∑n
j=1(Bj+B
′
j)
is symmetric, though it may or may not be in V . Let B0 be a shortest odd (simple) cycle
in G, and let B′0 be an orientation of B0 such that B
′
0 is a directed odd cycle. Let B
′
−1 be
the orientation of B0 that is opposite to the orientation of B′0 (i.e. B
′
−1 is B
′
0 with the arcs
reversed). Thus B′0 +B
′
−1 is a symmetric digraph with p (odd) double edges. Observe
b(B′−1 +B
′
0) + S +
n∑
j=1
(Bj +B′j) ∈ V,
where b is 0 or 1 according to whether the symmetric digraph S +
∑n
j=1(Bj +B
′
j) has an
even or odd number of double edges. Since π(C) = S + Y = S +
∑n
j=1Bj , the above
equation tells us
π(C)+V = b(B′−1+V) + b(B′0+V) +
n∑
j=1
(B′j+V). (5.4)
Recall that each B′j in this sum is either an anti-cycle or a simple directed odd cycle. Since
|C| ≥ q ≥ p we have |C| ≥ q = max{q, |B′0|} = wq(B′0), and similarly |C| ≥ wq(B′−1).
Also for 1 ≤ j ≤ n we have |π(C)| ≥ |B′j | by construction, so |C| ≥ max{q, |π(C)|} ≥
max{q, |B′j |} ≥ wq(Bj). Therefore
|C| ≥ wq(B′j) for − 1 ≤ j ≤ n. (5.5)
Now for each −1 ≤ j ≤ n we have B′j+V =
∑
i∈Jj (Ai+V) for an appropriate index set
Jj . Also it must be the case that
wq(B′j) ≥ wq(Ai) for every i ∈ Jj , (5.6)
for if wq(B′j) < wq(Ai) for some i and j we could exchange element Ai+V of basis A
with B′j+V , contradicting the fact that A is a minimum q-weight basis. Using Equation
118 Ars Math. Contemp. 2 (2009) 101–119
(5.4), we get
π(C)+V = b(B′−1+V) + b(B′0+V) +
n∑
j=0
(B′j+V)
= b
∑
i∈J−1
(Ai+V) + b
∑
i∈J0
(Ai+V) +
n∑
j=0
∑
i∈Jj
(Ai+V)
Comparing this with (5.3) and using (5.5) and (5.6), it follows that |C| ≥ wq(Ai) = |Ãi|
for each i ∈ I .
Case 2. Suppose |C| < q. Then C must be a cycle in G × (Cq − e) for some edge
e ∈ E(Cq). By Lemma 3.3 there is an edge ab ∈ E(Cq − e) for which
C = A+D (5.7)
where A ∈ C(G × ab) ⊆ C(G × Cq) and D ∈ D(G × (Cq − e)) ⊆ D(G × Cq), and
|C| ≥ |A|.
We claim that π(A) is an anti-cycle: WLOG assume b = a+ 1. Now, the degree of any
vertex (x, a) of A is even, so let its neighbors be (yi, b) for 1 ≤ i ≤ 2k for some integer
k. Then the set of arcs of form π((x, a)(yi, b)) = −→xyi are the outward-pointing arcs at the
vertex x of π(A), so the out-degree of x is even. Similarly, since the degree of vertex (x, b)
of A is even, the same argument shows that the in-degree of x is even. Thus π(A) is an
anti-cycle. Observe also that |A| = |π(A)| because any arc−→xy of π(A) can be the image of
only one edge (x, a)(y, b) of A. Since |C| ≥ |A|, we also have |C| ≥ |π(A)|= wq(π(A)).
Write π(A)+V as
π(A)+V =
∑
j∈J
(Aj+V), (5.8)
and observe that we must have wq(π(A)) ≥ wq(Aj) for each j ∈ J , for otherwise some
element Aj+V of the basis A could be exchanged for π(A)+V , violating the fact that A
is a minimal q-weight basis. Now take π′ of both sides of Equation (5.2) to get π′(C) =∑
i∈I(Ai+V). Since π′(C) = π′(A + D) = π′(A) = π(A)+V , we have π(A)+V =∑
i∈I(Ai +V). Comparing this with Equation (5.8), we have I = J . Since we have
established |C| ≥ wq(π(A)) ≥ wq(Aj) = |Ãj | for all j ∈ J , we now also have |C| ≥ |Ãi|
for all i ∈ I . This completes the proof.
This concludes our solution to the special case G× Cq of the general problem of con-
structing an MCB for G × H in terms of invariants of the factors. We believe the reader
may now have a sense of the complexity of such a general construction. We maintain hope
that someone will find a simple construction for the general case, though we expect that
such a construction would involve elements of our approach.
As noted in the introduction, the MCB problem has been resolved for the Cartesian,
strong and lexicographic products. To our knowledge, the modular product (see Appendix
C of [6]) is the only associative product that remains unexplored.
References
[1] F. Berger, Minimum Cycle Bases of Graphs, dissertation, Technische Universität München, 2004.
Z. Bradshaw and R. H. Hammack: Minimum cycle bases of direct products. . . 119
[2] Z. Bradshaw and M. M. M. Jaradat, Minimum cycle bases for direct products of K2 with com-
plete graphs, Australasian J. Comb., 43 (2009), 127–131.
[3] R. Diestel, Graph Theory, third ed., Springer-Verlag, Berlin, 2005.
[4] R. Hammack, Minimum cycle bases of direct products of bipartite graphs, Australasian J. Comb.
36 (2006), 213–221.
[5] R. Hammack, Minimum cycle bases of direct products of complete graphs, Information Process-
ing Letters 102 (4) (2007), 214–218.
[6] W. Imrich and S. Klavžar, Product Graphs; Structure and Recognition, Wiley Interscience Series
in Discrete Mathematics and Optimization, New York, 2000.
[7] W. Imrich and P. Stadler, Minimum cycle bases of product graphs, Australasian J. Comb. 26
(2002), 233–244.
[8] M. M. M. Jaradat, Minimum cycle bases of lexicographical products of graphs, Discussions
Mathematicae Graph Theory 28 (2) (2008), 229–247.
[9] M. M. M. Jaradat, On the basis number of the direct product of graphs, Australasian J. Comb.,
27 (2003), 293–306.
[10] D. J. A. Welsh, Kruskal’s theorem for matroids, Proc. Cambridge Phil. Soc. 64 (1968), 3–4.