Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 223–234
Minimum cycle bases of lexicographic products
Marc Hellmuth
Center for Bioinformatics, Saarland University
Building E 2.1, D-66041 Saarbrücken, Germany,
Philipp-Jens Ostermeier
Max Planck Institute for Mathematics in the Sciences
Inselstraße 22, D-04103 Leipzig, Germany
Peter F. Stadler
Bioinformatics Group, Department of Computer Science and
Interdisciplinary Center of Bioinformatics, University of Leipzig
Härtelstraße 16-18, D-04107 Leipzig, Germany
Max Planck Institute for Mathematics in the Sciences
Inselstraße 22, D-04103 Leipzig, Germany
Fraunhofer Institut f. Zelltherapie und Immunologie
Perlickstraße 1, D-04103 Leipzig, Germany
Inst. f. Theoretical Chemistry, University of Vienna
Währingerstraße 17, A-1090 Wien, Austria
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA
Received 6 September 2010, accepted 2 January 2012, published online 22 March 2012
Abstract
Minimum cycle bases of product graphs can in most situations be constructed from
minimum cycle bases of the factors together with a suitable collection of triangles and/or
quadrangles determined by the product operation. Here we give an explicit construction
for the lexicographic product G ◦ H that generalizes results by Berger and Jaradat to the
case that H is not connected.
Keywords: Cycle space, cycle basis, lexicographic product.
Math. Subj. Class.: 05C10
E-mail addresses: marc.hellmuth@bioinf.uni-sb.de (Marc Hellmuth), Philipp.Ostermeier@mis.mpg.de
(Philipp-Jens Ostermeier), studla@bioinf.uni-leipzig.de (Peter F. Stadler)
Copyright c© 2012 DMFA Slovenije
224 Ars Math. Contemp. 5 (2012) 223–234
1 Introduction
Throughout this contribution, let G = (V,E) be a finite undirected simple graph. A
(generalized) cycle in G is an Eulerian subgraph of G, i.e., a subgraph of G in which
the degree of every vertex is even. A connected Eulerian subgraph in which every vertex
has degree 2 will be called an elementary cycle.
The cycle space C(G) of a graph G is the subspace of the edge space generated by the
elementary cycles. Hence we regard cycles as subsets of E(G). A cycle basis is a basis
of C(G). If G has c(G) connected components, C(G) has dimension β(G) = |E(G)| −
|V (G)|+ c(G). An minimum cycle basis (MCB) is a cycle basis B that minimizes the total
length
`(B) =
∑
C∈B
|E(C)| (1.1)
of the basis cycles. MCBs play a role e.g. in the analysis of electrical circuits, periodic
scheduling problems in traffic planning, graph drawing [18, 14], mechanical frame analysis
[13], biopolymer structures [17, 4, 16], and computational chemistry [2, 15].
Four standard graph products have received considerable attention [9, 8]: the Cartesian,
direct, strong and lexicographic product of graphs. MCBs of these product graphs can in
most cases be constructed from MCBs of their factors and a suitable collection of short
cycles that can quite easily be specified explicitly. A complete characterization for the
Cartesian and the strong product can be found in [10]. The situation is more complex
for the direct product of simple graphs. Constructions for MCBs are known for bipartite
factors [5], products of complete graphs [6, 3], and graphs of the form G× Cq where G is
connected non-bipartite and Cq is an odd cycle [7]. MCBs for the lexicographic product
G ◦ H consist of a single copy of the MCB of G and suitable set of triangles provided
H is connected [1, 11]. Here, we derive an MCB for lexicographic products G ◦ H with
a disconnected 2nd factor by combining the Berger-Jaradat construction for connected H
with an MCB of G ◦Kn, where Kn is the graph on n vertices without edges.
The lexicographic product G ◦ H has the vertex set V (G ◦ H) = V (G) × V (H).
There is an edge {(a, x), (b, y)} ∈ E(G ◦ H) if {a, b} ∈ E(G) or a = b and {x, y} ∈
E(H). The connectivity of G ◦H is therefore determined by the connectivity of G unless
G = K1. More precisely, let Gi, i ∈ I be the connected components of G and assume
Gi 6= K1. Then the connected components of G ◦H are the lexicographic products Gi ◦
H , irrespective of whether H is connected or not. Since K1 ◦ H = H , the connected
components are determined by H in this case. For convenience, we write x◦H and ab◦H
for the lexicographic product of H with the K1 consisting of the single vertex x and the
K2 consisting of the single edge {a, b}, respectively. The Gx-layer (or Gx-fiber) is the
subgraph of G ◦H induced by the vertices of the form (a, x), a ∈ V (G). Analogously, the
Ha-layer is the subgraph induced by the vertices of the form (a, x), x ∈ V (H). We will
write B for a cycle basis of G and Bx denotes the copy of B within the Gx-layer. The set
{v ∈ V (G) | {a, v} ∈ E(G)} of all neighbors of a vertex a is denoted by N(a).
Remark 1.1. Since the cycle space of a graph is the direct sum of the cycle spaces of its
connected components we can assume in the following that without loss of generality G is
connected and is distinct from K1.
In order to determine whether a given cycle basis is an MCB we use the following
well-known criterion, see e.g. [7].
M. Hellmuth et al.: Minimum cycle bases of lexicographic products 225
Lemma 1.2. A cycle basis B for a graph G is an MCB if and only if every cycle C ∈ C(G)
is a sum of basis elements whose lengths do not exceed |E(C)|.
2 MCB of G ◦ Kn
In order to show how to construct MCBs of products of disconnected graphs, we are in
this section concerned with the special simpler instance G ◦ Kn. Let us first consider
the case that G is triangle-free. In this case G ◦ Kn is also triangle-free. We start with
the observation that K2 ◦ Kn = Kn,n. As shown by Kainen [12], Kn,n has an MCB
K consisting entirely of quadrangles. Setting V (K2) = {a, b} and fixing a vertex x0 ∈
V (Kn) the (n − 1)2 quadrangles of K are of the form 〈(a, x0)(b, x0)(a, u)(b, v)〉 with
u, v 6= x0. For arbitrary graphs G and a fixed edge {a, b} ∈ E(G) we will denote the
elements 〈(a, x0)(b, x0)(a, u)(b, v)〉, u, v 6= x0 of K by Kab.
Remark 2.1. In the following, we will denote the fixed vertex that determines a particular
Kainen basis by x0.
Now consider, for each vertex a ∈ V (G) a set of quadrangles of the form Cvbc :=
〈(b, x0)(a, x0)(c, x0)(a, v)〉 where x0 is again the fixed vertex in V (Kn), b and c are
neighbors of a in G. Clearly, {a, b} ∈ E(G) and {a, c} ∈ E(G), and v 6= x0. Not
all such combinations of b and c are linearly independent. In particular, we observe that
Cvbc ⊕ Cvbd = Cvcd. Thus, consider the star graph consisting of a and its neighbors N(a) in
G and fix an arbitrary b ∈ N(a). It follows that
Ga :=
{
Cvbc|c ∈ N(a) \ {b}, v ∈ V (Kn) \ {x0}
}
(2.1)
is linearly independent because each cycle contains an edge {(a, v), (c, x0)}, that is not
contained in any other cycle of Ga.
Lemma 2.2. The cycle set Q :=
⋃
ab∈E(G)
Kab ∪
⋃
a∈V (G)
Ga is linearly independent.
Proof. Since the |E(G)| copies of the Kn,n are pairwise edge disjoint we see that the
|E(G)|(n−1)2 cycles inK := ⋃ab∈E(G)Kab are linearly independent. Furthermore, since
each cycle in Gu contains an edge that is not contained in any other cycle in Gv, v 6= u, we
can conclude that the
∑
a∈V (G)(deg(a) − 1) = 2|E(G)| − |V (G)| cycles in
⋃
a∈V (G) Ga
are linearly independent.
The symmetric difference of any two distinct quadrangles in
⋃
ab∈E(G)Kab results in a
cycle that contains at least one elementary cycle. Notice that there is at least one elementary
cycle that is entirely contained in a subgraph ab ◦Kn for some edge {a, b} ∈ E(G), since
the elements of the Kainen basis of different sets Kuv and Kxy are edge disjoint. W.l.o.g.
let C be such a cycle that contains the elementary cycle c = 〈(a, s1)(b, s2) . . . (a, s2j−1)
(b, s2j)〉 with si ∈ V (Kn), j ≤ l. By construction and since |c| ≥ 4, we can conclude that
c contains an edge {(a, sf ), (b, sg)} with sf , sg 6= x0.
Now, we use elements from
⋃
a∈V (G) Ga for the construction of c. We observe that the
edge {(a, sf ), (b, sg)} is not included in any cycle of
⋃
a∈V (G) Ga. Hence, the symmetric
difference of cycles in
⋃
a∈V (G) Ga never contains an elementary cycle in ab ◦Kn for any
edge {a, b} ∈ G. Consequently, span(⋃ab∈E(G)Kab) ∩ span(⋃a∈V (G) Ga) = ∅ and
hence, Q is a linearly independent set.
226 Ars Math. Contemp. 5 (2012) 223–234
Theorem 2.3. Let B be an MCB of a graph G. If G 6= K1 is a connected triangle-free
graph, then Q∪ Bx0 is an MCB of G ◦Kn.
Proof. We show first that no cycle within the Gx0 -fiber can be generated by elements of
Q. Suppose that such a cycle C exists. W.l.o.g. let {(a, x0), (b, x0)} and {(b, x0), (c, x0)}
be two consecutive edges of C. In order to generate these edges we can only use squares
contained in Kab and Kbc, resp., or squares contained in Gb, Ga, and Gc.
If we use the square S1 = 〈(a, x0), (b, x0), (a, xi), (b, xj)〉 ∈ Kab or S2 = 〈(b, x0),
(c, x0), (b, xl), (c, xk)〉 ∈ Kbc, we must finally remove the edges {(a, xi), (b, xj)} and
{(b, xl), (c, xk)}, which is only possible if we compute S1⊕S1 or S2⊕S2, a contradiction.
If we use one of the squares in Ga, Gb, or Gc, e.g. 〈(b, x0), (c, x0), (d, x0), (c, xr)〉 ∈
Gc, we must remove the edge {(b, x0), (c, xr)}, which is only possible by using a square
〈(b, x0), (c, x0), (b, xs), (c, xr)〉 ∈ Kbc. By the same arguments as above, it follows that
this square must be used twice in order to cancel the remaining edge {(b, xs), (c, xr)}. The
same holds for the other squares contained in Gb and Ga. Therefore, we cannot generate a
cycle C that is within the Gx0 -layer using elements of Q and hence, Q ∪ Bx0 is linearly
independent.
Since G is triangle-free, the cycles of minimal length are quadrangles. Q consists of
|Q| = |E(G)|(n− 1)2 +
∑
a∈V (G)
(deg(a)− 1)(n− 1) =
|E(G)|(n− 1)2 + (2|E(G)| − |V (G)|)(n− 1)
elements. Together with the β(G) cycles of Bx0 this equals the required number of β(G ◦
Kn) = |E(G)|n2 − |V (G)|n+ 1 basis cycles. Hence, Q∪ Bx0 is a basis.
It remains to show that the constructed basis is minimal. To show this we first observe
that by construction Bx0 is an MCB of span(Bx0) and by Lemma 1.2 Q is an MCB of
span(Q). Since Q ∪ Bx0 is a basis no cycle entirely contained in the x0-fiber can be
constructed as linear combination of Q and no cycle in span(Q) is a linear combination
of cycles from Bx0 . As a consequence, C ∈ C(G ◦ Kn) can be written in the form C =
C ′ ⊕ C ′′ where C ′ ∈ span(Bx0) and C ′′ ∈ span(Q). By construction of Q we can
conclude that the number of edges of C ′′ contained in (G ◦Kn) \Gx0 is greater or equal
than the number of its edges in Gx0 . More formally, n1 = |E(C ′′) ∩ E(G ◦ Kn) \
E(Gx0)| ≥ |E(C ′′) ∩ E(Gx0)| = n2 and therefore, n1 − n2 ≥ 0. Hence, we have
|E(C)| = |E(C ′)| + n1 − n2 ≥ |E(C ′)|. Since Bx0 is an MCB of span(Bx0), we can
conclude that |E(C)| ≥ |E(C ′)| ≥ |E(BC)| with BC ∈ Bx0 . Moreover, since G is
triangle-free and all elements of Q have length four it holds for every BC ∈ Bx0 and each
QC ∈ Q that |E(C)| ≥ |E(C ′)| ≥ |E(BC)| ≥ |E(QC)|. Therefore, Lemma 1.2 implies
that the length of the cycle basis Q ∪ Bx0 cannot be reduced by exchanging any of its
elements by C; hence Q∪ Bx0 is an MCB.
3 The general case
Let us now suppose that H consists of ` ≥ 1 connected components H1, . . . ,H`. For
each component Hi of H fix a vertex yi ∈ V (Hi). Without loss of generality, we set
y1 = x0, where x0 is the chosen vertex in the Kainen basis. We denote this set of fixed
vertices by Wfix. The quadrangles of Kab are of the form 〈(a, x0)(b, x0)(a, yi)(b, yj)〉 with
yi, yj ∈Wfix. Ga is defined as the set {Cvbc|c ∈ N(a) \ {b}, v ∈Wfix \ {x0}}.
M. Hellmuth et al.: Minimum cycle bases of lexicographic products 227
Let F be a maximal spanning forest (w.r.t. the number of edges it contains) of H . We
now define an arbitrary orientation on all edges of G, so that {a, b} is oriented from a to b.
We construct the following sets of triangles.
1. For each edge {a, b} ∈ E(G) we set
Tab = {〈(a, y), (b, u), (b, v)〉 | y ∈ V (H), {u, v} ∈ E(F )}. (3.1)
2. Consider all triangles of the form {〈(a, u), (a, v), (b, yi)〉 | yi ∈ Wfix, {u, v} ∈
E(F )}. For each edge {a, b} ∈ E(G) we set
T ′ab =
⋃
yi∈Wfix
{〈(a, u), (a, v), (b, yi)〉 | {u, v} ∈ E(F )}. (3.2)
3. Set T ′ =
⋃
ab∈E(G)(Tab ∪ T ′ab).
4. For each a ∈ V (G) fix an edge {a, b} and the vertex x0 ∈ V (H) that is the same x0
as for the choice of the Kainen basis. Set
Ta = {〈(a, u), (a, v), (b, x0)〉 | {u, v} ∈ E(H)− E(F )}. (3.3)
5. Set T ′′ =
⋃
a∈V (G) Ta.
6. Set T = T ′ ∪ T ′′.
Note that for ` = 1, F is a spanning tree of H and T coincides with the triangle set
of the Berger-Jaradat MCB for the case of connected H . Furthermore, for each Hi all
necessary triangles of MCBs of G ◦ Hi are produced by the above construction since the
connected components of F are spanning trees of the corresponding components of H ,
hence TG◦Hi ⊆ T . The linear independence of T follows from almost the same arguments
as in the connected case:
Lemma 3.1. The set T = T ′ ∪ T ′′ is a linearly independent set.
Proof. First, for a fixed edge {a, b} it is easy to see that Tab is a linearly independent
set, since all triangles 〈(a, y), (b, u), (b, v)〉 contain different edges {(b, u), (b, v)}, u, v ∈
E(F ) for a fixed y ∈ V (H). All triangles that contain the same edge {(b, u), (b, v)} are
connected to different y ∈ V (H). We therefore cannot generate a triangle 〈(a, x), (b, u),
(b, v)〉 ∈ Tab from triangles 〈(a, y), (b, u), (b, v)〉 ∈ Tab. The reason is that there are no
elements in Tab that could shift (a, y) to (a, x), since this would require cycles with edges
in theHa-layer. Analogously, one shows that the triangles 〈(a, u), (a, v), (b, yi)〉 contained
in T ′ab are linearly independent. Ta is a set of linearly independent circuits because every
triangle contains an edge {(a, u), (a, v)} with {u, v} ∈ E(H) − E(F ) that belongs to no
other triangle in Ta.
Next, we demonstrate that for a fixed edge {a, b} ∈ E(G) the set Tab ∪ T ′ab ∪ Ta ∪ Tb
is linearly independent.
First, we check that Tab ∪T ′ab is linearly independent. To see this, notice that each C ∈
span(Tab) contains an edge {bu, bv} or at least two vertices in one connected component
Hbi of the H
b-layer, but every cycle in span(T ′ab) contains at most one vertex in this H
b
i ,
because yi is fixed.
228 Ars Math. Contemp. 5 (2012) 223–234
Second, Tab ∪ T ′ab ∪ Ta is linearly independent, since every triangle contained in Ta
contains edges {(a, u), (a, v)} with {u, v} ∈ E(H) − E(F ) that are by construction not
contained in any triangle of Tab ∪ T ′ab.
Third, Tab ∪ T ′ab ∪ Ta ∪ Tb is linearly independent, since each triangle contained in Tb
contains edges {(b, u), (b, v)} with {u, v} ∈ E(H) − E(F ) that are by construction not
contained in any triangle of Tab ∪ T ′ab ∪ Ta.
Finally, T = ⋃ab∈G(Tab∪T ′ab∪Ta∪Tb) is linearly independent. To see this, notice that
each triangle in Tab ∪ T ′ab ∪ Ta ∪ Tb for a fixed edge {a, b} ∈ E(G) is a triangle in ab ◦H .
Moreover, any nontrivial linear combination of triangles in Tab ∪T ′ab ∪Ta ∪Tb contains an
edge {(a, x), (b, y)} that cannot be cancelled by any triangles in Ta′b′ ∪ T ′a′b′ ∪ Ta′ ∪ Tb′
with (a′, b′) 6= (a, b). Thus, T = T ′ ∪ T ′′ is a linearly independent set.
a b c
0
1
2
a0 b0 c0
a1 b1 c1
a2 b2 c2
Tab
x0
y1
y2
x1 y1
y2 x2
y1
y2
T ′ab y0
x1
x2
y1x1
x2
Q
x0 y0
y1x1
a0 b0 c0
b1
Figure 1: An MCB of the lexicographic product depicted in the upper left part. In this
example we have {x, y} ∈ {{a, b}, {b, c}}, T ′′ = ∅, and Bx0 = ∅.
We will show in the following that the union of T , Q and a copy of an MCB of G that
is located in a Gx0 -layer is an MCB of G ◦H if G is triangle-free.
Theorem 3.2. Suppose that G 6= K1 is a connected, not necessarily triangle-free graph
and H has connected components Hi, 1 ≤ i ≤ ` and let B be an MCB of G. Then
T ∪ Q ∪ Bx0 is a cycle basis of G ◦H .
M. Hellmuth et al.: Minimum cycle bases of lexicographic products 229
Proof. First, we verify that T ∪ Q ∪ Bx0 has the required cardinality:
|T ∪ Q ∪ Bx0 | =
= |E(G)|(|V (H)|(|V (H)| − `) + `(|V (H)| − `)︸ ︷︷ ︸
T ′
+ |V (G)|(|E(H)| − |V (H)|+ `)︸ ︷︷ ︸
T ′′
+ |E(G)|(`− 1)2 + (`− 1)(2|E(G)| − |V (G)|)︸ ︷︷ ︸
Q
+ |E(G)| − |V (G)|+ 1︸ ︷︷ ︸
Bx0
= (|E(G)||V (H)|2 + |V (G)||E(H)|)− |V (G)||V (H)|+ 1 = β(G ◦H)
Second, we prove that T ∪ Q is linearly independent. A cycle that is in span(Q)
contains no edge and at most one vertex of each Hai -layer with a ∈ V (G). But a cycle in
span(T ) contains an edge or at least two vertices in an arbitrary Hai -layer. To see this, let
C1 ∈ T be an elementary cycle that contains an edge e in one Hai -layer and let C2 ∈ T .
If e /∈ E(C2) than C1 ⊕ C2 is a cycle with e in Hai . If e ∈ E(C2) then C1 ⊕ C2 has two
vertices in Hai . By induction one can easily verify that every cycle C ∈ span(T ) contains
an edge or at least two vertices in an arbitrary Hai -layer. Now, we have to examine two
cases:
1. C ∈ span(T ) is a cycle that has two vertices and no edges in any Hvj . Then C1 ⊕C
is a cycle with an edge e in Hai .
2. C ∈ span(T ) contains a walk in some Hvj -layer. Now, the symmetric difference
with elementary cycles C ′ ∈ T that contain an edge of this walk results in a cycle
that has at least two vertices in some Hwk -layer.
Therefore, we cannot construct a cycle C of span(T ) by elements of span(Q) since none
of its circuits contain an edge in any Hai -layer.
Furthermore, we cannot generate elements of span(Bx0) with elements of span(T ∪Q)
because a cycle in span(T ∪Q) always contains an edge of the form {(a, xi), (b, xj)} with
xi 6= xj .
Theorem 3.3. Suppose G 6= K1 is triangle-free, H has connected components Hi, 1 ≤
i ≤ `, and B is an MCB of G. Then T ∪ Q ∪ Bx0 is an MCB of G ◦H .
Proof. In Theorem 3.2 we proved that T ∪Q∪Bx0 is a cycle basis ofG. Hence, it remains
to show that this basis has minimal length.
Note, we cannot construct a triangle only with elements ofQ or Bx0 . To see this, notice
that every triangle in G ◦ H has to contain an edge of a connected component Hai of the
Ha-layer, since G is triangle-free. Furthermore, such an edge is by construction neither
contained in Q nor in Bx0 . Hence, for the construction of triangles in G ◦H we need the
triangles contained in T .
Assume we could generate triangles in G ◦H using elements of T and elements of Q
or Bx0 .
First, we cannot construct a triangle by elements of span(T ) and elements of span(Q),
since the resulting cycle has always length l ≥ 4.
Second, we cannot construct a triangle by elements of span(T ) and by elements of
span(Bx0), since the symmetric difference with cycles in span(Bx0) only adds, changes
230 Ars Math. Contemp. 5 (2012) 223–234
or deletes paths in the particular Gx0 -layer. Hence, a cycle from Bx0 is no generator of
any triangle because the attribute of changing or deleting paths in the Gx0 -layer would
only be interesting to generate triangles with edges in the Gx0 -layer, which is triangle-free.
Furthermore, all triangles that have an edge in the Gx0 -layer are by construction already in
T .
Thus, the only way to generate triangles in G ◦H is to use triangles of T only. Further-
more, β(G ◦H) is the number of elements in T ∪Q∪Bx0 which are linearly independent.
Hence, T ∪ Q ∪ Bx0 is an MCB of G ◦H .
The construction used in Theorems 3.2 and 3.3 is an MCB only if G is triangle-free.
If G contains triangles, however, it becomes possible to obtain a shorter basis by replacing
certain quadrangles by triangles. In the following we modify our construction to accommo-
date this case and replace the set Q resulting in a new set QF. We do this in two separate
steps.
First, we replace Ga by a suitably selected set of squares G̃a. Then we show how some
of the elements of G̃a and of the Kainen basis
⋃
ab∈E(G)Kab can be replaced by appropriate
triangles.
Step 1 (Ga → G̃a).
Consider a spanning forest F of the induced subgraph 〈N(a)〉 in G that consists of the
trees F1, . . . , F`, ` ≥ 1. We define for a fixed x0
G′a = {〈(u, x0)(a, x0)(w, x0)(a, v)〉 | {u,w} ∈ E(F ), x0 ∈ V (H)}.
We have |G′a| = |E(F )| = |N(a)| − ` = deg(a) − ` with ` ≥ 1. Furthermore |Ga| =
deg(a) − 1. To obtain the required dimension we therefore need to add ` − 1 additional
elements if we replace Ga. Therefore, we define the set G′′a that will be used in addition
if ` − 1 > 0 as follows: Let b ∈ N(a) ∩ V (Fi) be a fixed vertex for some i = 1 . . . `.
Now fix for each tree Fj , j 6= i a vertex cj . The set G′′a is defined as the set of all squares
〈(b, x0)(a, x0)(cj , x0)(a, v)〉 with x0, v ∈ V (H), v 6= y. Hence, |G̃a| = deg(a)− 1. Note
that G′a = ∅, if G does not contain any triangles. In this case G′′a and Ga coincide. Finally,
we set
Q∗ :=
⋃
ab∈E(G)
Kab ∪
⋃
a∈V (G)
G̃a
Step 2
Let {a, b} ∈ E(G) be an edge that is contained in k ≥ 1 triangles in G. Now, we
fix exactly one vertex c that is contained in one of those triangle 〈abc〉 in G. For each
such edge {a, b} ∈ E(G) and this fixed vertex c one replaces all Kainen basis elements
〈(a, x0)(b, x0)(a, xi)(b, xj)〉 ∈ Kab by triangles 〈(c, x0)(a, xi)(b, xj)〉. We denote this
modified set byR.
Let 〈asatau〉 be a triangle that is contained in G. Replace all squares 〈(as, x0)(at, x0)
(au, x0)(at, xj)〉 ∈ ∪a∈V (G)G̃a that contain two edges of this triangle in the Gx0 -layer by
the triangles 〈(as, x0)(at, xj)(au, x0)〉. This modified set will be denoted by S.
Finally, we set
QF := R∪ S .
Notice that |Q| = |Q∗| = |QF|.
M. Hellmuth et al.: Minimum cycle bases of lexicographic products 231
0
1
a b
c
a0 b0
c0
a1 b1
c1
Bx0
b0a0
c0
S
c0b0
a1
c0a0
b1
b0a0
c1
R
c1b1
a0
c1a1
b0
b1a1
c0
Figure 2: The MCB T ∪QF ∪Bx0 of the lexicographic product G ◦H depicted in the left
part, where T = ∅. The former setQ constructed for triangle-free factors G consists of the
quadrangles 〈(a, 0)(b, 0)(a, 1)(b, 1)〉, 〈(a, 0)(c, 0)(a, 1)(c, 1)〉, 〈(b, 0)(c, 0)(b, 1)(c, 1)〉,
〈(a, 0)(c, 0)(b, 0)(b, 1)〉, 〈(a, 0)(b, 0)(c, 0)(b, 1)〉 and 〈(b, 0)(a, 0)(c, 0)(a, 1)〉.
Theorem 3.4. LetG 6= K1 be an arbitrary connected graph and supposeH has connected
components Hi, 1 ≤ i ≤ `. Furthermore, let B be an MCB of G. Then T ∪ Q∗ ∪ Bx0 is a
cycle basis of G ◦H .
Proof. First, we show that all elements of the former set Ga can be generated by the ele-
ments of G̃a.
W.l.o.g., we can choose the vertex b ∈ N(a) ∩ V (Fi) of G′′a as the same vertex b as
chosen for Ga. The quadrangles of G′′a are of the form 〈(b, x0)(a, x0)(cj , x0)(a, v)〉 with
cj ∈ Fj , i 6= j. If i = j, i.e., the vertices b and cj are in the same component in the
maximal spanning forest, then 〈(b, x0)(a, x0)(cj , x0)(a, v)〉 is contained in G′a.
Let V (Fj) = {cj1 , . . . , cjl} and, w.l.o.g., let cj = cj1 for each Fj .
If |V (Fj)| = 1, then the cycle 〈(b, x0)(a, x0)(cj , x0)(a, v)〉 ∈ Ga is already contained
in G′′a .
Let C = 〈(b, x0)(a, x0)(cjt , x0)(a, v)〉 be an arbitrary cycle in Ga and assume that
|V (Fj)| > 1. Note, there is a unique path between the vertices cj1 and cjt in Fj . More-
over, for any two adjacent vertices cjs and cjt with s, t ≤ l in Fj there exists a square
〈(cjs , x0)(a, x0)(cjt , x0)(a, v)〉 in G′a. Therefore, we have
〈(b, x0)(a, x0)(cjt , x0)(a, v)〉 =〈(b, x0)(a, x0)(cj1 , x0)(a, v)〉
⊕
t⊕
i=1
〈(cji−1 , x0)(a, x0)(cji , x0)(a, v)〉 .
Thus, one can generate all elements of Ga by the elements of G̃a. Moreover, since |G̃a| =
|Ga|, we conclude that T ∪ Q∗ ∪ Bx0 is a cycle basis of G ◦H .
Theorem 3.5. LetG 6= K1 be an arbitrary connected graph and supposeH has connected
components Hi, 1 ≤ i ≤ `. Furthermore, let B be an MCB of G. Then T ∪ QF ∪ Bx0 is
an MCB of G ◦H .
232 Ars Math. Contemp. 5 (2012) 223–234
Proof. First, we show that T ∪QF∪Bx0 is a basis of G◦H . To this end, we show that we
can generate the replaced elements ofQ∗ by elements ofQF. Consider a triangle 〈asatau〉
in G. For a triangle ∆s,t,u = 〈(as, x0)(at, xi)(au, x0)〉 ∈ S in G ◦H holds:
∆s,t,u = 〈(as, x0)(at, x0)(au, x0)(at, xi)〉 ⊕ 〈(as, x0)(at, x0)(au, x0)〉
where 〈(as, x0)(at, x0)(au, x0)(at, xi)〉 ∈ ∪a∈V (G)G̃a ⊆ Q∗. This implies that
〈(as, x0)(at, x0)(au, x0)(at, xi)〉 = ∆s,t,u ⊕ 〈(as, x0)(at, x0)(au, x0)〉 .
If a triangle has exactly one edge in theGx0 -layer and is not a basis cycle, w.l.o.g. 〈(as, x0)
(at, x0)(au, x3)〉, then we can generate it by basis triangles.
In the course of constructing S we employed the forest F . In F there is a unique path
P = (as, x0)(b1, x0) . . . (bp, x0)(at, x0) defining triangles that have an edge in P and that
are connected to (au, x3). This leads to the following equation:
∆s,t,u = 〈(as, x0)(at, x0)(au, x3)〉
= 〈(as, x0)(b1, x0)(b2, x3)〉 ⊕
p−1⊕
i=1
〈(bi, x0)(au, x3)(bi+1, x0)〉
⊕ 〈(bp, x0)(at, x0)(au, x3)〉
⊕ 〈(as, x0)(b1, x0) . . . (bp, x0)(at, x0)〉,
where 〈(as, x0)(b1, x0) . . . (bp, x0)(at, x0)〉 denotes the cycle consisting of the edges in
E(P ) and the edge {(as, x0), (at, x0)}.
For a triangle ∆′s,t,u = 〈(as, x0)(at, xi)(au, xj)〉 ∈ R in G ◦H holds:
∆′s,t,u =〈(as, x0)(at, x0)(au, x0)(at, xj)〉 ⊕ 〈(au, x0)(as, x0)(at, x0)(au, xi)〉
⊕ 〈(as, x0)(at, x0)(as, xi)(at, xj)〉 ⊕ 〈(as, x0)(at, x0)(au, x0)〉.
This implies that:
〈(as, x0)(at, x0)(as, xi)(at, xj)〉 =
= 〈(as, x0)(at, x0)(au, x0)(at, xj)〉︸ ︷︷ ︸
∆s,t,u⊕〈(as,x0)(at,x0)(au,x0)〉
⊕∆′s,t,u⊕
〈(au, x0)(as, x0)(at, x0)(au, xi)〉︸ ︷︷ ︸
∆u,s,t⊕〈(as,x0)(at,x0)(au,x0)〉
⊕〈(as, x0)(at, x0)(au, x0)〉
= ∆′s,t,u ⊕∆s,t,u ⊕∆u,s,t ⊕ 〈(au, x0)(as, x0)(at, x0)〉
Moreover, since |Q∗| = |QF| we conclude that T ∪ QF ∪ Bx0 is a cycle basis of G ◦H .
In order to demonstrate minimality of this basis, it remains to show that no triangle can
be generated by quadrangles. By the same argument as in Theorem 3.3 we can conclude
that every triangle in ab ◦H , where {a, b} ∈ E(G) is not contained in any triangle of G,
can only be generated by elements of T . If {a, b} ∈ E(G) is contained in a triangle of
G, we have to show that no triangle in ab ◦ H can be generated by squares contained in
QF ∪ Bx0 .
M. Hellmuth et al.: Minimum cycle bases of lexicographic products 233
We already proved that we can generate all triangles that are completely included or
have an edge in one connected component j of an Ha-layer by triangles in T . Hence,
it remains to prove that we can generate all triangles whose vertices are in different Ha-
layers.
The following equation shows, how we can generate all triangles whose vertices are in
different Ha-layers with xi ∈ Wfix. Note, in this equation we generate triangles 〈(a1, x1)
(a2, x2)(a3, x3)〉 by a sum of quadrangles and one triangle. For the used quadrangles we
have already shown above how one can generate them by triangles only. The triangle
〈(a1, x1)(a2, x2)(a3, x3)〉 can be generated by the following sum:
〈(a1, x0)(a2, x0)(a1, x1)(a2, x2)〉 ⊕ 〈(a3, x0)(a2, x0)(a3, x3)(a2, x2)〉
⊕ 〈(a1, x0)(a3, x0)(a1, x1)(a3, x3)〉 ⊕ 〈(a1, x0)(a2, x0)(a3, x0)(a2, x2)〉
⊕ 〈(a2, x0)(a3, x0)(a1, x0)(a3, x3)〉 ⊕ 〈(a3, x0)(a1, x0)(a2, x0)(a1, x1)〉
⊕ 〈(a1, x0)(a2, x0)(a3, x0)〉
In the following we show how a triangle 〈(a1, z1)(a2, z2)(a3, z3)〉 with zi, xi ∈ Hi can
be generated, in which zi must not necessarily be in Wfix. For each zi exists a path Pi =
zi1 . . . zip with zi1 = zi and zip = xi ∈ Wfix. As shown in the proof of Theorem 3.3, all
triangles 〈(ai, zij )(as, zs)(ai, zik)〉 and 〈(ai, zij )(at, zt)(ai, zik)〉 and {zij , zik} ∈ E(Hi)
can be constructed by triangles of T only. Therefore, the triangle 〈(a1, z1)(a2, z2)(a3, z3)〉
can be generated by the following sum:
〈(a1, x1)(a2, x2)(a3, x3)〉⊕
⊕
⊕
{u,v}∈E(P1)
(〈(a1, u)(a3, x3)(a1, v)〉 ⊕ 〈(a1, u)(a2, x2)(a1, v)〉)
⊕
⊕
{u,v}∈E(P2)
(〈(a2, u)(a1, z1)(a2, v)〉 ⊕ 〈(a2, u)(a3, x3)(a2, v)〉)
⊕
⊕
{u,v}∈E(P3)
(〈(a3, u)(a1, z1)(a3, v)〉 ⊕ 〈(a3, u)(a2, z2)(a3, v)〉).
Since there is no triangle in G ◦H that is generated by cycles with length l > 3 that are
contained in T ∪ QF ∪ Bx0 , we can conclude that T ∪ QF ∪ Bx0 is an MCB.
References
[1] F Berger, Minimum cycle bases of graphs, PhD thesis, Technische Universität München, 2004.
[2] F. Berger, C. Flamm, P. M. Gleiss, J. Leydold and Peter F. Stadler, Counterexamples in chemi-
cal ring perception, J. Chem. Inf. Comput. Sci. 44 (2004), 323–331.
[3] Z. Bradshaw and M. M. M. Jaradat, Minimum cycle bases for direct products of k2 with
complete graphs, Australas. J. Comb. 43 (2009), 127–131.
[4] P. M. Gleiss, J. Leydold and P. F. Stadler, Interchangeability of relevant cycles in graphs, Elec.
J. Comb. 7 (2000), R#16, Santa Fe Institute preprint 99-07-046.
[5] R. Hammack, Minimum cycle bases of direct products of bipartite graphs, Australasian J.
Comb. 36 (2006), 213–221.
[6] R. Hammack, Minimum cycle bases of direct products of complete graphs, Inf. Processing
Lett. 102 (2007), 214–218.
234 Ars Math. Contemp. 5 (2012) 223–234
[7] R. Hammack and Z. Bradshaw, Minimum cycle bases of direct products of graphs with cycles,
Ars Math. Contemp. 2 (2009), 101–119.
[8] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and its Applications, CRC Press, 2nd edition, 2011.
[9] W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics
and Optimization, Wiley-Interscience, New York, 2000.
[10] W. Imrich and P. F. Stadler, Minimal cycle bases of product graphs, Australasian J. Comb. 26
(2003), 233–244.
[11] M. M. M. Jaradat, Minimal cycle bases of the lexicographic product of graphs, Discuss. Math.,
Graph Theory 28 (2008), 229–247.
[12] Paul C. Kainen, On robust cycle bases, Electronic Notes Discr. Math. 11 (2002), 430–437, The
Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and
Applications June 4-9 2000, Kalamazoo, MI.
[13] A. Kaveh and R. Mirzaie, Minimal cycle basis of graph products for the force method of frame
analysis, Commun. Numer. Methods Eng. 24 (2008), 653–669.
[14] T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt and K. A. Zweig,
Cycle bases in graphs: Characterization, algorithms, complexity, and applications, Comp. Sci.
Review 3 (2009), 199–243.
[15] Ch. J. Lee, Y.-M. Kang, K.-H. Cho and K. T. Noac, A robust method for searching the smallest
set of smallest rings with a path-included distance matrix, Proc Natl Acad Sci USA 106 (2009),
17355–17358.
[16] S. Lemieux and F. Major, Automated extraction and classification of RNA tertiary structure
cyclic motifs, Nucleic Acids Res. 34 (2006), 2340–2346.
[17] J. Leydold and P. F. Stadler, Minimal cycle basis of outerplanar graphs, Elec. J. Comb., 5
(1998), 209–222, R#16.
[18] C. Liebchen and R. Rizzi, Classes of cycle bases, Discr. Appl. Math. 155 (2007), 337–355.