ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 123-140
Convex cycle bases
Marc Hellmuth
Center for Bioinformatics, Saarland University Building E 2.1, D-66041 Saarbrücken, Germany
Josef Leydold *
Institute for Statistics and Mathematics, WU, Augasse 2-6, A-1090 Wien, Austria
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 Wahringerstraße 17, A-1090 Wien, Austria Center for non-coding RNA in Technology and Health, University of Copenhagen Gr0nnegardsvej 3, DK-1870 Frederiksberg, Denmark Santa Fe Institute, 1399 Hyde ParkRd., Santa Fe, NM 87501, USA
Received 29 August 2011, accepted 30 January 2013, published online 4 April 2013
Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs.
Keywords: cycle basis, convex subgraph, isometric subgraph, Cartesian product, partial cubes Math. Subj. Class.: 05C15, 05C10
* corresponding author
E-mail addresses: marc.hellmuth@bioinf.uni-sb.de (Marc Hellmuth), josef.leydold@wu.ac.at (Josef Leydold), studla@bioinf.uni-leipzig.de (Peter F. Stadler)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
106
ArsMath. Contemp. 7 (2014) 123-121
1 Introduction and basics
The cycle space C(G) of a simple, unweighted, undirected graph G = (V, E) consists of all its Eulerian subgraphs (or generalized cycles), i.e., all the subgraphs of G for which every vertex has even degree. It is convenient in this context to interpret subgraphs of G as edge sets. The generalized cycles form a vector space over GF(2) with vector addition X © Y := (X U Y) \ (X n Y) and scalar multiplication 1 • X = X, 0 • X = 0, for X,Y e C(G). This vector space is generated by the elementary cycles of G, i.e., the connected subgraphs of G for which every vertex has degree 2. A basis B of the cycle space C is called a cycle basis of G = (V, E) [9]. The dimension of the cycle space is the cyclomatic number p(G) (or first Betti number). For a connected graph we have ^(G) = |E | — |V | + 1. Notice that the cycle space of a graph is the direct sum of the cycle spaces of its 2-connected components.
Cycle bases of graphs have diverse applications in science and engineering. Examples include structural flexibility analysis [27], electrical networks [11], chemical structure storage and retrieval systems [15], scheduling problems [36], graph drawing [33], andbiopoly-mer structures [34, 35]. Surveys and extensive references can be found in [19, 22, 28, 37].
A convexity space (V, C) [6] consists of a ground set V and a set C of subsets of V satisfying
(C1) 0 e C, V e C, and
(C2) K', K" e C implies K' n K" e C.
For a simple, undirected graph G with vertex set V, every set p of paths on G defines a convexity space (V, C(p)) in the following way: A set of vertices K is p-convex, K e C(P), if and only if, for every path P e P with both end vertices in K, all vertices of P are contained in K. This construction is discussed in detail in [14]. Several special types of paths p have been studied in this context, most prominently the set of all paths [5], the set of all triangle paths [8], the set of all induced paths [13], and the set of all shortest paths [39].
We will be concerned here only with the latter definition of convexity, usually known as geodetic convexity, see Section 2 for a formal definition. Geodetically convex cycles play an important role in the theory of Cartesian graphs products and their isometric subgraphs. The absence of convex cycles longer than 4, for example, characterizes semi-median graphs [3]. Such long convex cycles furthermore play a role e.g. in Euler-type inequalities for partial cubes [31].
It appears natural, hence, to investigate whether there is a connection between the cycle space and the (geodetic) convexity space of a graph G = (V, E). Note that the cycle space is defined on the edge set, while the convexity space is defined on the vertex set. Intuitively, this connection is made possible by the fact that induced elementary cycles in G are characterized by either their vertex sets or their edge sets.
Definition 1.1. A convex cycle basis of a graph G is a cycle basis that consists of convex elementary cycles.
We briefly consider a generalized definition of convex cycle bases relaxing the requirement for elementary basis cycles in the final section.
Cycle bases with special properties have been investigated in much detail in the literature. Examples include minimum cycle bases [2, 17, 19, 29, 44], (strictly) fundamental
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
125
cycle bases [20, 32, 38], or (quasi) robust cycle bases [26, 40]. Here, we consider convex cycle bases. We show that convex cycle bases are not related to other types of cycle bases, we introduce a polynomial-time algorithm to compute a convex cycle basis for an arbitrary input graph, and we construct a class of graphs with convex cycles bases by means of Cartesian products that in particular includes partial cubes.
2 Geodetic convexity and characterization of convex cycles
For a graph G we denote the vertex set and edge set of G by V(G) and E(G), respectively. Similarly, we write C(G) for the cycle space of G. An edge that joins vertices x and y is denoted by the unordered pair {x, y}. The lengths |P| and |C| of a path P and a cycle C in G, respectively, is the number of their edges. For simplicity, we will refer to a path with end vertices u and v as uv-path. The distance distG(u, v) between two vertices u and v of G is the length of a shortest uv-path. It is well known that this distance forms a metric on V. The set of all shortest uv-paths will be denoted by PG [u, v]. The cardinality of this set, i.e., the number of shortest uv-paths, will be denoted by Suv = |PG [u, v] |. A modification of Dijkstra's algorithm computing both the distance matrix of G and the matrix S is given in the appendix.
A subgraph H of G is isometric if distH(u, v) = distG(u, v) holds for all u,v G V(H). We say that H is a (geodetically) convex subgraph of G if for all u, v G V(H), all shortest uv-paths P G PG[u, v] are contained in H. In the following, convex will always mean geodetically convex. The empty subgraph will be considered as convex. The intersection of convex subgraphs of G is again a convex subgraph of G [42].
Since H is an isometric subgraph of G if and only if H contains at least one P G PG[u, v] for every pair u, v G V(H), we see that convex implies isometric. Furthermore, if H is an isometric subgraph of G, it is in particular an induced subgraph of G. Finally, the connectedness of G implies that all its isometric subgraphs are connected. Our first result characterizes elementary convex cycles.
Lemma 2.1. Let C be an elementary cycle of G.
If |C | is odd, then C is convex if and only if for every edge e = {x, y} in C there is a unique vertex z in C such that distG(x, z) = distG(y, z) = (|C| — 1)/2 and Sxz = Syz = 1. If |C | is even, then C is convex if and only if for every edge e = {x, y} in C there is a unique edge h = {u,v} in C such that (i) distG(x,u) = distG(y, v) = |C|/2 — 1, (ii) distG(x, v) = distG(y, u) = |C|/2, (iii) Sxu = Syv = 1, and (iv) SXv = Syu = 2.
Proof. Suppose C is convex. Consider two vertices p and q in C with distG (p, q) < |C|/2. If C is convex, then the unique shortest path between p and q must run along C, so that Spq = 1. Clearly, this condition characterizes convex cycles provided C is odd.
The situation is more complicated for even cycles. Let us first suppose that C is convex and fix an arbitrary edge {x, y}. In an even elementary cycle there is a unique edge h = {u, v} satisfying (i) distC(x,u) = distC(y, v) = |C|/2 — 1, (ii) distC(x,v) = distC(y, u) = |C|/2. Isometry of C implies that properties (i) and (ii) are satisfied. The argument of the preceding paragraph shows that (iii) holds. For x, the only point in C at distance |C|/2 is v. Thus there are two paths P' and P" in C of length distG(x, v) = |C|/2. By the convexity of C, these paths are contained in C (so that C = P' U P") and must be the only shortest paths connecting x and v; hence consequently Sxv = 2. An analogous argument shows that Syu = 2.
106
ArsMath. Contemp. 7 (2014) 126-121
In order to prove the converse, consider an even elementary cycle C satisfying (i) through (iv). Again we fix an arbitrary edge {x, y} of C. Since C is even, there is a unique antipodal point v of x and a unique antipodal point u of y with distC(x,v) = distC(y, u) = |C|/2. We claim that {u, v} is the required edge. If this were not the case, then there would be some other edge with both endpoints closer to x along C than v that satisfies condition (ii). This is impossible, however, since for such a vertex v' we would have |C|/2 = distG(x, v') < distC(x, v') < distC(x,v) = |C|/2. We easily check that distC (x, u) = |C|/2 -1 and distC (y,v) = |C|/2 -1. By property (i), therefore, the paths from x to u and from y to v along C are shortest paths in G. Furthermore, the two paths from x to v along C via either u or y are also shortest paths in G by property (ii). Thus distC (x, q) = distG(x, q) for all vertices q in C. Repeating this argument for all x in C shows that C is isometric. By property (iii), the shortest path from x to u is unique. Since all sub-paths of shortest paths are again shortest path, this is also true for all vertices q in C along the shortest path from x to u. The same is true for all q in C along the unique shortest path from v to y. By property (iv), finally, there are exactly two shortest paths from x to v. We have already seen that two of these run along either half of the cycle C. The same is true for the two paths connecting y with u. Thus all shortest path connecting a vertex q in C with either x or y are contained in C. Repeating the argument for all edges {x, y} in C shows that C is convex.	□
A direct consequence of Lemma 2.1 is that a cycle C in G can be efficiently tested for convexity provided both the distance matrix and the matrix S containing the number of shortest paths have been pre-computed: it suffices to verify, in constant time, the conditions of the lemma for each antipodal pair of edges or pair of edge and vertex, respectively. The test thus requires O(|C|) time provided that C is given as ordered list of its vertices. As a simple corollary of Lemma 2.1 we have
Corollary 2.2. Let C be an elementary convex cycle of G. Then, for every e = {x,y} G C there is a vertex z in C such that C = P' U P'' U {x, y}, P' G PG [x, z], and P'' G PG [y, z].
A closely related, but much weaker, condition appears in the theory of minimal cycles bases [22]:
Definition 2.3. A cycle C is edge-short if it contains an edge e = {x, y} and a vertex z such that C = Cxy,z := {x, y} U Pxz U Pyz where Pxz and Pyz are shortest paths.
Corollary 2.4. If C is an elementary convex cycle of G then it is edge-short. 3 Convex cycle bases
Corollary 2.2 sets the stage for enumerating all elementary convex cycles in a graph. The following result establishes an upper bound and provides a polynomial time algorithm for this purpose.
Theorem 3.1. Any graph G = (V, E) contains at most |E||V| elementary convex cycles. These can be constructed and listed in O(|E||V|2) time.
Proof. Every pair of an edge e = {x, y} and a vertex z specifies at most one elementary convex cycle in the following way: If distG(x, z) = distG(y, z) and Sxz = Syz = 1 we set
Cez := Pxz U Pyz U {x, y}. If distG (x, z) = distG (y, z) + 1, Sxz = 2 and Syz = 1, then
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
127
we choose a neighbor u of z such that distG(x, u) = distG(y, z), Sux — 1 and Suy — 2, and set Cez :— Pxu U {u, z} U Pyz U {x, y}. Note that the choice of u is unique if C is convex. The selection of these |E| |V | candidates thus requires O(|E | |V |2) time.
In order to efficiently retrieve each candidate cycle in O(|C|) time given {x,y} and z we need the to know the predecessor nsu of u on the shortest path from s to u. Note that this information is needed only if Ssu — 1. The modified Dijkstra algorithm in the Appendix computes this array without changing the asymptotic complexity of the shortest path algorithm. Since each candidate cycle can then be checked for convexity in O(|C|) time, the total effort to extract all elementary convex cycles is in O (| E|| V|2).	□
This algorithm outlined in the proof of Theorem 3.1 can be regarded as a variant of Vismara's construction of prototypes of candidates for relevant cycles [44]. The fact that the number of elementary convex cycles in G is bounded by | V| |E| immediately implies that a convex cycle basis can also be found in polynomial time:
Corollary 3.2. For each graph G — (V, E) it can be decided whether G has a convex cycle basis, and if so, a convex cycle bases can be constructed, in O(|E |2 |V | ^(G)2) time.
Proof. Since the cycles of a graph form a matroid, the canonical greedy algorithm can be applied to find a maximum set of linearly independent elementary convex cycles, see e.g. [21]. G has a convex cycle basis if and only if this set has size ^(G) — |E| - |V| + 1. For each of the at most | V| |E| candidate cycles, this requires a test of linear independence with a partial basis that is not larger than ^(G) — |E| - |V| + 1, i.e., O(|E|). Applying Gaussian elimination for this purpose, the total effort is bounded by O(|E| |V|2) + O(|E|2 |V|m(G)2) — O(|E|2 |V|m(G)2) time.	□
There are graphs that do not have a convex cycle basis. The complete bipartite graph K2 3 is the simplest counter example (see Fig. 1). None of its three cycles (all have length 4) is convex.
Figure 1: None of the cycles in K2,3 is convex.
4 Relation of convex cycle bases to other types of cycle bases
Although we have an efficient algorithm to test whether a graph has a convex cycle basis, it will be interesting to characterize the class of graphs that admit convex cycle bases. However, we first investigate the relation between convex cycle bases and other types of cycle bases.
A procedure analogous to Corollary 3.2 was introduced in [22] for the purpose of retrieving minimal cycle bases from a candidate set of edge-short cycles. One would expect, therefore, that convex cycle bases and minimal cycles bases are closely related.
106
ArsMath. Contemp. 7 (2014) 128-121
Convex cycle bases of a graph need not have the same length. Consider the graph that is obtained from the cube Q3 where one edge is contracted. Then the four quadrangles and two triangles are convex and five of these form a convex cycle basis. Thus convex bases contain either exactly one or two triangles and thus may have different lengths.
The length ¿(B) of a cycle basis B is the sum of the lengths of its generalized cycles: ¿(B) = J2CeB |C|. A minimum cycle basis M is a cycle basis with minimum length. The generalized cycles in M are chord-less cycles (see [22]). Hence, we may consider elementary cycles instead of generalized cycles in the remaining part of this section. For the sake of completeness we note that a minimum cycle basis is a cycle basis in which the longest cycle has the minimum possible length [10].
The set R of relevant cycles of a graph is the union of its minimum cycle bases [41,44]. In analogy to convex cycle bases one may want to consider isometric cycle bases, i.e., cycle bases consisting of isometric cycles.
Lemma 4.1. All relevant cycles of a graph are isometric. Thus every minimal cycle basis is an isometric cycle basis.
Proof. We start from Lemma 2 of [44]: If P is a subpath of a relevant cycle C such that |P| < 1 |C|, then P is a shortest path. It follows that every relevant cycle is isometric, and hence every minimal cycle basis of G consists of elementary isometric cycles.	□
Theorem 4.2. If G has a uniquely defined minimal cycle basis, then this minimal cycle basis is convex.
Proof. Assume that G has a unique minimal cycle basis B. By Lemma 4.1 the cycles of B are necessarily isometric. Now suppose that C G B is not convex. Then there exist two vertices u, v g C and (at least) three edge disjoint uv-paths P, P' and P'' such that |P| > |P'| = |P"| and C = P U P'. Hence there are two cycles Ci = P U P" and C2 = P' U P" with |C| = |Ci| > |C21. By construction C, Ci, and C2 are linearly dependent and thus one of Ci or C2 cannot be represented as sum of cycles in B \ {C}. Hence we get a new cycle basis B' = (B\{C}) U{C '} where C ' is either Ci or C2. In either case we find ¿(B') < ¿(B) a contradiction to our assumption that B is the unique minimal cycle basis.	□
As a consequence, we can conclude that Halin graphs that are not necklaces [43] and outerplanar graphs [35] have a convex cycle basis.
The converse of Theorem 4.2 is not true, however, as Figure 2 shows. This graph has a convex cycle basis but its minimal cycle basis is not uniquely defined. Even worse, none of its minimal cycle bases is convex.
A cycle basis B = {Ci,..., CM(-G)} of G is called fundamental [20, 46] if there is an ordering n such that for 2 < k < ^(G):
Fundamental cycle bases are obtained from ear decomposition, suggesting that there could be a relation between convex and fundamental cycles bases. Champetier's graph [4], however, has a cycle basis consisting entirely of triangles, which obviously is convex. On the other hand, this basis is not fundamental [1]. Conversely, fundamental cycle bases need not be convex, as shown, e.g., by the planar basis of K2,3.
(4.1)
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
129
Figure 2: The cyclomatic number of the graph is 7. All minimal cycle bases consist of the two triangles, all quadrangles that do not contain the upper dashed edge and two of the three quadrangles that contain the upper dashed edge (which also includes the outer cycle). However, two of these three quadrangles that contain the upper dashed edge are not convex. Hence none of the minimal cycle bases is a convex cycle basis.
On the other hand there is a unique convex cycle basis that consists of all triangles, all quadrangles that do not contain the upper dashed edge, the outer quadrangle and the cycle of length 5 at the bottom.
5 Convexity in subgraphs and intersections
This section contains some auxiliary results which we will need for our investigation of isometric subgraphs in Section 6 below.
Lemma 5.1. Let M be an isometric (convex) subgraph of G and F C M be a subgraph of M. Then F is isometric (convex) in M if and only if it is isometric (convex) in G.
Proof. If F is an isometric subgraph of G, then for each pair of vertices u, v e V (F), F contains a shortest uv-path. Since F C M, this path is also a shortest uv-path in M and hence F is isometric in M. If F is a convex subgraph of G, then it contains all shortest uv-paths which are also shortest paths in M and thus F is convex in M.
Now assume that F is not isometric in G. Then there exist two distinct vertices u, v e V(F) C V(M) such that there are shortest uv-paths P in G with |P| < distF(u, v). At least one of these paths must be contained in M since M is an isometric subgraph of G. Thus F cannot be an isometric subgraph of M, either. If F is not convex in G then there exist two distinct vertices u, v e V(F) C V(M) such that there is at least one shortest uv-path P which is not contained in F. Since M is convex, P must be contained in M and thus F cannot be convex in M, either.	□
Lemma 5.2. Let M be an isometric subgraph of G and F be a convex subgraph of G. Then F n M is convex in M.
Proof. For each pair of vertices x, y e V(F) n V(M), F contains all shortest xy-path in G. Since M is an isometric subgraph of G it must contain at least one of these and thus the proposition follows.	□
Lemma 5.3. Assume that G has a convex cycle basis. Let M be a convex subgraph of G that has a convex cycle basis BM. Then BM can be extended to a convex cycle basis BG of G.
106
130	ArsMath. Contemp. 7 (2014) 123-140
Proof. By Lemma 5.1 the cycles in BM are convex subgraphs of G. By assumption there exists a convex cycle basis B'G of G. By the Austauschsatz we can replace appropriate cycles in B'G by the cycles in BM. Thus we obtain a convex cycle basis BG of G which
Figure 3 shows that the converse of this lemma is not true in general: a convex subgraph of a graph that has a convex cycle basis need not necessarily have a convex cycle basis.
Figure 3: The cyclomatic number of this graph is |E| — | V| + 1 = 16 - 9 + 1 = 8. The three triangles and the five quadrangles that do not entirely consist of dashed edges form a convex cycle basis. The subgraph that consists of the dashed edges is convex but does not have a convex cycle basis (see Fig. 1).
6 Isometric subgraphs of Cartesian products
In this section, we will be concerned with the Cartesian product GDH and its isometric and convex subgraphs. The Cartesian product has vertex set V(GDH) = V(G) x V(H); two vertices (xG, xH) and (yG, yH) are adjacent in GDH if {xG, yG} e E(G) and xH = yH, or {xH, yH} e E(H) and xG = yG. For detailed information about product graphs we refer the interested reader to [18, 24].
For the Cartesian product GDH the subgraph Gv induced by all vertices (x, v) with x e V(G) and a fixed vertex v e V(H) is called a layer of G (or G-layer) in GDH. The projection nG : GDH ^ G is the usual weak homomorphism defined as (x, y) e V(GDH) ^ x e V(G). Note that edges in G-layers are mapped into edges in G and edges in H-layers are mapped into vertices in G.
There is a close relationship between (geodetic) convexity and Cartesian products, see [7] for a general result. The fundamental result for this purpose is the distance lemma.
Proposition 6.1 (Distance Lemma, [23]). Let x = (xG, xH) and y = (yG, yH) be arbitrary vertices of the Cartesian product GDH. Then
Moreover, if P is a shortest xy-path in GDH, then nG(P) is a shortest xGyG-path in G.
It seems natural that convexity properties of products also hold for layers and projections.
v^y^ics m Bg uy me ^y^ics ni b
such that BM C Bg as claimed.
□
distgDH(x, y) = distg(xG, yg) + distH(xh, Vh) .
Lemma 6.2 ([24]). The layers Gv and Hw are convex subgraphs of the Cartesian product GDH. Moreover, if F is an isometric (convex) subgraph of GDH, then for all v e V (H)
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
131
and w G V (G) the following holds: F n Gv and F n Hw are isometric (convex) subgraphs of F, Gv and Hw, respectively.
Corollary 6.3. Let M be an isometric subgraph of GDH. If (xG, xH) and (yG, yH) are two vertices in M with xG = yG, then there exists a shortest xHyH-path in M n HXG. Moreover, all shortest (xG, xH)(yG, yH)-paths in M are contained in HXG.
Another consequence of the distance lemma is the following auxiliary result.
Lemma 6.4. Let P be a shortest xy-path in GDH. Then nG(P) is a path with |nG(P)| = distG (xG, yG) = veH |P n Gv |, where the last term is the total number of edges of P in G-layers. The result holds analogously for nH (P).
Proof. If (w, xH) and (w, yH) are two distinct points of P, then by Corollary 6.3 all shortest xH yH -paths are contained in layer Hw. Consequently, there cannot be two distinct edges e1 and e2 in G with nG(e1) = nG(e2) that belong to P since otherwise P also must contain two shortest paths in different H-layers that connect corresponding vertices of these edges, that is, P would contain a cycle. Hence all vertices of nG(P) have degree 2 except its end vertices which have degree 1 (or 0 in the case where nG(P) is a single vertex). Thus nG(P) is path of length |nG(P)| = distG(xG,yG) = J2v^H |P n Gv |, as claimed.	□
Lemma 6.5. For every isometric (convex) subgraph F of GDH, nG(F) is an isometric (convex) subgraph of G.
Proof. Let x = (xG,xH) and y = (yG,yH) be two vertices in F. If F is isometric in GDH, then there exists a shortest xy-path P in F. By the distance lemma, nG(P) is a shortest xGyG-path in G and contained in nG(F). Thus nG(F) is an isometric subgraph of G. Now if nG(F) is not convex in G, then there exists a shortest xGyG-path PG in G that is not contained in nG(F). Let PH be a shortest xHyH-path in H. Then P = PGD{xh} U PHD{yG} is a shortest xy-path as its length is |P| = distG(xG, yG) + distH(xH, yH) = distGnH(x, y). However, by construction P cannot be contained in F and hence F is not convex in GDH. Consequently, if F is convex in GDH, then nG(F) is convex in G, as claimed.	□
On the other hand convexity and isometry properties of factors are also propagated to their Cartesian product. The following result is well-known and holds for more general notions of convexity.
Lemma 6.6 ([7]). If F and M are convex subgraphs of G and H, respectively, then FDM is a convex subgraph ofGDH.
The last lemma also holds for isometric subgraphs.
Lemma 6.7. If F and M are isometric subgraphs of G and H, respectively, then FDM is an isometric subgraph ofGDH.
Proof. Immediate corollary of the distance lemma.	□
We now want to extend convex cycle bases of two graphs G and H to a cycle basis of their Cartesian product GDH. Let TG and TH denote spanning trees of G and H, respectively. Let
Bn = {eDf: e G E(G), f G th} U {eDf: e G tg, f G E(H)} . (6.1)
132
ArsMath. Contemp. 7 (2014) 123-140
Then for fixed vertices v e V(H) and w e V(G) and respective cycle basis BG and BH
is a cycle basis of GDH [25].
Theorem 6.8. Let G and H be two graphs that have convex cycle bases BG and BH, respectively. Then their Cartesian product GDH has a convex cycle basis that can be constructed using Eq. (6.2).
Proof. Notice that all quadrangles in Bq are convex subgraphs in GDH. By Lemma 5.1 Cv is a convex cycle in GDH. Thus we get a convex cycle basis of GDH by means of basis (6.2) when both BG and BH are convex cycle basis.	□
Remark 6.9. An analogous statement for the strong product (see [18]) is not true, as the strong product of an elementary cycle and an edge K2 shows.
We have seen in Figure 3 that a convex subgraph of a graph that has a convex cycle basis does not necessarily have a convex cycle basis. However, a more restrictive property appears to propagate under the formation of Cartesian products: we consider the class of graphs for which every convex subgraph has a convex cycles basis.
Theorem 6.10. Let G be a graph that has a convex cycle basis. Then every isometric subgraph M of GDK2 with nG(M) = G has a convex cycle basis.
For the proof of this theorem we need some intermediate results.
Lemma 6.11. Let C be an isometric elementary cycle in GDH. Then one of the following holds:
(1)	nG(C) = K1, i.e., a single vertex, or
(2)	nG(C) = K2, i.e., a single edge, or
(3)	nG(C) is an isometric elementary cycle in G.
Proof. Notice that nG(C) = |J v£V (H) nG(C n Gv). Let x = (xg,xh ) and y = (yG ,yu) be two vertices in C with xG = yG and xH = yH. Analogously to the proof of Lemma 6.4 no vertex v in nG (C) can have degree greater than 2. Now if C C Hw for some w e V (G), then nG(C) = {w} = K1, i.e., case (1). If there is a vertex x where nG(x) has degree 1, then there exist two distinct vertices u,v e V(H) such that nG(C n Gu) and nG(C n Gv) have a common edge e. However, this only can happen if nG(C) = {e} = K2, i.e., for case (2). Otherwise, there would be two vertices y' and y" in C so that nG (y') = nG (y") is adjacent to nG(x) with vertex degree larger than 1 in the projection, contradicting isometry of C. If we have neither case (1) nor case (2), then all vertices of nG(C) have degree 2 and hence nG(C) is an elementary cycle which is isometric in G by Lemma 6.5, i.e., case
Now let C be an elementary cycle in G and M be an isometric subgraph of GDK2. Let Z(C, M) denote the set of elementary cycles C' ç M that are convex in M and satisfy
nG (C') = C. We set Z (C, M ) = 0 if no such cycle exists.
{Cv : C G Bg} U {Cw : C G BH} U Ba
(6.2)
(3).
□
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
133
Lemma 6.12. Let M be an isometric subgraph of GDK2 and let C e G be a convex elementary cycle with C C nG(M). Then Z(C, M) is non-empty.
Proof. First notice that CDK2 is a convex subgraph of GDK2 by Lemma 6.6. M' = M n (CDK2) is isometric in CDK2 by Lemma 5.1 and convex in M by Lemma 5.2. Let M1 and M2 denote the respective intersections of M' with the two K2-layers of CDK2. If M1 = C (or M2 = C) then M1 (M2) is a convex elementary cycle in C□K by Lemma 6.2, and thus also in M' by Lemma 5.2. Otherwise, both M1 and M2 are paths of length |M4| < ±|C| for i = 1, 2, since M' is isometric. As nG(M') = C, nC(M1) U nC(M2) = C. Consequently, as M' is isometric, M' is an elementary cycle that is trivially convex in M'. In all cases Z(C, M') is non-empty. Since Lemma 5.1 implies that Z(C, M') C Z(C, M), the proposition follows.	□
Remark 6.13. The arguments in the proof of Lemma 6.12 together with the distance lemma also show that the elements of Z(C, M) form the set of all shortest cycles C in M with the property nG (C') = C.
Proof of Theorem 6.10. Let BG be a convex cycles basis of G. Let Bq be as in (6.1) and define BZ be a set of cycles that contains exactly one cycle C' e Z (C, M) for each C e BG. By Lemma 6.12 all these sets Z (C,M) are non-empty. Clearly, the cycles in Bq UBz are linearly independent and thus form a cycle basis of GDK2. Now let BM be the set of all cycles in Bq U Bz that are contained in M. By construction all cycles in BM are convex subgraphs of M and BZ C BM. Thus it remains to show that |BM| = ^(M). Let mG and mK2 denote the numbers of edges in (GDK2) \ M that lie in G-layers and K2-layers, respectively. Let n be the number of vertices in (GDK2) \ M. Since nG(M) = G and M is an isometric subgraph of GDK2 we find that mK2 = n. Thus ^(M) = (|E (GDK2)| — m G — mK2) — (|V (GOK )| — n) + 1 = |E(GD K2)| — |V (G^)| + 1 — mG = M(GDK2) — mG. On the other hand, there are exactly mG cycles in Bq that are not contained in M and hence |BM | = ^(GDK2) — mG = ^(M), i.e., BM is a cycle basis of M. This finishes the proof of the theorem.	□
We easily can generalize Theorem 6.10 to arbitrary isometric subgraphs of GDK2.
Theorem 6.14. Let G be a graph such that every isometric subgraph has a convex cycle basis. Then every isometric subgraph of GDK2 also has a convex cycle basis.
Proof. Let H be an isometric subgraph of GDK2. By Lemma 6.5, G' = nG (H) is an isometric embedding into G and thus has a convex cycle basis by our assumptions. Hence by Theorem 6.10 every isometric subgraph M of G'DK2 C GDK2 has a convex cycle basis.	□
Theorem 6.14 has quite strong implications. A d-dimensional hypercube is the d-fold product of K2 by itself, Qd = □d=1K2. Partial cubes are isometric subgraphs of Qd and form a very rich graph class that contains hypercubes, trees, median graphs, tope graphs of oriented matroids, benzenoid graphs, tiled partial cubes, netlike partial cubes, and flip graphs of point sets that have no empty pentagons; see [30, 31] and references therein. As K2 has a convex cycle basis (namely 0) we immediately obtain the following results by a recursive application of Theorem 6.14.
Theorem 6.15. Partial cubes have a convex cycle basis.
134
ArsMath. Contemp. 7 (2014) 123-140
Theorem 6.16. Let G be a graph such that every isometric subgraph has a convex cycle basis and let Q be any partial cube. Then every isometric subgraph of GDQ has a convex cycle basis.
Proof. Let G be as claimed. Theorem 6.14 implies that every isometric subgraph of GQK2D • • • DK2 = GDQ„ has a convex cycle basis. Lemma 6.7 implies that GDQ is an isometric subgraph of GDQ„. Moreover, Lemma 5.1 implies that every isometric subgraph of GDQ is an isometric subgraph of GDQ„ and thus, has a convex cycles basis.	□
Figure 4 shows that the class covered by Theorem 6.16 is much larger than the class of partial cubes. Recall that partial cubes are characterized by the so-called Djokovic-Winkler-Relation ©: Two edges e = {u, v} and f = {x, y} are in relation ©, (ef) G ©, if dist(u, x) + dist(v, y) = dist(u, y) + dist(v, x). A graph is a partial cube if and only if it is bipartite and the relation © is an equivalence relation [47].
Figure 4: Observe that (eie2) G © and (e2e3) G ©, but (eie3) G ©. Thus © is not an equivalence relation. Therefore, this bipartite graph is not a partial cube. However, it has a convex cycle base consisting of the three planar faces.
It seems natural that Theorem 6.16 should remain true also for a more general type of Cartesian products. We state this as
Conjecture 6.17. Let G1 and G2 be graphs such that each of their isometric subgraphs have convex cycle bases. Then every isometric subgraph of G1DG2 has a convex cycle basis.
A further step towards a proof of this conjecture is given by the following special case:
Theorem 6.18. Let G be a graph such that every isometric subgraph has a convex cycle basis and let Cn be an elementary cycle. Then every isometric subgraph of GDCn has a convex cycle basis.
Notice that this theorem is an immediate corollary of Theorem 6.16 if n is even since cycles of even length are partial cubes [30, 45]. The proof of the general case is present after Lemma 6.19 below. For this purpose we first have to introduce a graph operation for the case when C is a cycle of odd length. So assume that C = C2k-1 for some integer k > 2. First fix three vertices u, v, w G V(C) with {u, v}, {v, w} G E(C2k-1). Create a new cycle C = C2k by splitting vertex v, that is, replace v by two vertices v' and v" and the edges {u, v}, {v, w} by three edges {u, v'}, {v', v''}, {v'', w}.
This splitting operation can be generalized to subgraphs F of GDC. In essence, we replace F n Gv by (F n Gv )DK2. In more detail, we introduce the graph operations T and its converse T* as follows: For a fixed vertex v g C, and any subgraph
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
135
F C GDC, we obtain the subgraph T(F) C GDC' by splitting all vertices (x, v) G F with x G G in the following way: Replace vertex (x, v) by (x, v') and (x, v''), and replace the edges {(x, u), (x, v)}, {(x, v), (x, w)}, and {(x, v), (y, v)}, when present, by the corresponding edges {(x,u), (x, v')}, {(x, v'), (x, v'')}, {(x, v''), (x,w)}, {(x,v'), (y, v')} and {(x, v''), (y, v'')}. Conversely, for a subgraph F' C BDC' we obtain the subgraph T*(F') C GDC by contracting all edges {(x, v'), (x,v'')} G E(GDC') and remove possible double edges. This construction in particular has the property that T(GDC) = GDC' and T* (GDC') = GDC.
Lemma 6.19. Let C = C2fe-i be an elementary cycle of odd length 2k — 1. If P is a shortest xy-path in GDC, then T(P) contains a shortest x'y'-path P' in GDC' where x' and y' are vertices in T(x) and T(y), resp.
Proof. Let x = (xG,xC) and y = (ya,yc) be two vertices in GDC and let x' = (x'G, x'C,) and y' = (yG, y'/) be two vertices in T(x) and T(y), resp. Let P' be a shortest x'y'-path in T(P). We have to show that P' is also a shortest x'y'-path in GDC'. Observe that Lemma 6.4 implies that |nG(P)| = |nG(P')| and |nc (P)| = |nc (P')| — J(P') where £(P') = 1 if (P') contains edge {v',v''} and J(P') = 0 otherwise. Moreover, distc (xC,yC) < k — 1 and distC/ (x'C,, y'/) < k. Now suppose that P' is not a shortest x'y'-path in GDC'. Then there exists a x'y'-path P'' that is strictly shorter than P', that is, |nc (P'')| < |nc (P')| < k. As P is a shortest xy-path we have |nc(T*(P''))| = |nc(T*(P'))| = |nc(P)| < k —1. Again |nc(T*(P''))| = |nc(P'')| — J(P''). Consequently (P'') must contain edge {v', v''} while (P') must not. Therefore nc (P'') n ic (P') = C'. However |nc (P'')| + |nc (P')| < k + k = 2k = |C'|, a contradiction. This completes the proof.	□
Proof of Theorem 6.18. Let C be an odd cycle. Thus C' is even and hence a partial cube. Lemma 6.19 implies that T(M) is an isometric subgraph of GDC' if M is an isometric subgraph in GDC. In this case, T(M) has a convex cycle basis B'. Now consider a convex cycle D' G B'. Lemma 6.11 implies that T*(D') is either an elementary cycle or T*(D') is a single edge in layer Gv. The latter happens if and only if D' contains edges {(x, v'), (x, v'')} and {(y, v'), (y, v'')}. In this case D' must be a convex quadrangle. There are |E(M n Gv )| quadrangles of this type, and they form an linearly independent set Q of convex cycles. Thus we can assume, w.l.o.g., that they all are contained in B'. Lemma 6.19 implies that Y* (D') is a convex subgraph of M. Thus let
B := {T*(D')|D' g B' and Y*(D') is an elementary cycle} .
The cycles in B are linearly independent: Consider any linear combination of the form J2i AjT* (D') = 0. It follows that there is a corresponding linear combination J2i ^D' = J2j ijQj, where Qj G Q is a quadrangle that is contracted to 0 by T*. Since B' is linearly independent by assumption, all ij and Ai must be 0, however.
It remains to show that |B| = ^(M). Observe that T(M) contains the subgraph induced by vertices (x, v') and (x, v'') if (v,x) G V(M) for some x G G. Otherwise T(M) contains none of these two vertices. Thus we find for the cyclomatic number ^(M) = ^(T(M)) — |E(M n Gv)|. On the other hand |B| = |B'| — |E(M n Gv)| = m(t(M)) — |E(M n Gv)| = ^(M). This completes the proof.	□
136
ArsMath. Contemp. 7 (2014) 123-140
7 Convex Eulerian graphs that are not cycles
Convex cycles need not be elementary, even though they are necessarily connected when G is connected. Furthermore, the elementary cycles whose union forms convex Eulerian subgraph need not be convex themselves. An example is the K2,4, which can be decomposed into two elementary but not convex squares. In fact, the sum of convex cycles typically is not convex:
Lemma 7.1. Let C and C2 be two convex cycles in G. If C\ © C2 is 2-connected, then C © C2 is not convex.
Proof. If Ci © C2 is 2-connected, then it contains at least two distinct vertices u, v e V(Ci) n V(C2). Since Ci n C2 is also convex, it contains the set of all shortest uv-path which cannot be empty as u = v. Consequently, Ci © C2 = (Ci U C2) \ (Ci n C2) cannot contain any of these shortest path and is thus not convex.	□
If Ci © C2 is convex for two convex cycles Ci and C2, then Ci © C2 = Ci U C2 and connected (but not 2-connected). Thus V(Ci) n V(C2) consists of a single vertex. Notice, however, that even then Ci © C2 need not be convex.
One may ask, therefore, whether the cycle space of a graph that does not have a convex cycle basis nevertheless may have a basis consisting of convex Eulerian subgraphs. The example in Figure 5 shows that this is indeed possible.
Figure 5: The 6 triangles and the whole graph are all convex cycles and form a cycle basis. However, there is no convex cycle basis according to Definition 1.1: none of the elementary cycle that pass through the square node is convex.
Acknowledgements
The authors thank Sandi Klavzar for the inspiration to investigate convex cycle bases. This work was performed under the auspices of the EuroGIGA project GReGAS. The German sub-project of GReGAS is supported by the Deutsche Forschungsgemeinschaft (DFG) Project STA850/11-1. The Austrian participation in GReGAS is not supported by the Austrian Science Fonddation (FWF).
References
[1] F. Berger, C. Flamm, P. M. Gleiss, J. Leydold and P. F. Stadler, Counterexamples in chemical ring perception, J. Chem. Inf. Comput. Sci. 44 (2004), 323-331.
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
137
[2]	F. Berger, P. Gritzmann and S. de Vries, Minimum cycle bases for network graphs, Algorith-mica 40 (2004), 51-62.
[3]	B. Bresar, Characterizing almost-median graphs, Eur. J. Comb. 28 (2007), 916-920.
[4]	C. Champetier, On the null-homotopy of graphs, Discrete Math. 64 (1987), 97-98.
[5]	M. Changat, S. KlavZar and H. M. Mulder, The all-paths transit function of a graph, Czechoslovak. Math J. 51 (2001), 439-448.
[6]	M. Changat, S. Klavzsar, H. M. Mulder and A. Vijayakumar, Convexity in discrete structures, Ramanujan Mathematical Society Lecture Notes Series, Vol. 5, International Press of Boston, 2010.
[7]	M. Changat, H. M. Mulder and G. Sierksma, Convexities related to path properties on graphs, Discrete Math 290 (2005), 117-131.
[8]	M. Changat, G. N. Prasanth and J. Mathews, Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math. 309 (2009), 1575-1583.
[9]	W.-K. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math. 20 (1971), 525529.
[10]	D. M. Chickering, D. Geiger and D. Heckerman, On finding a cycle basis with a shortest maximal cycle, Inform. Processing Let. 54 (1994), 55-58.
[11]	L. O. Chua and L. Chen, On optimally sparse cycle and coboundary basis for a linear graph, IEEE Trans. Circuit Theory 20 (1973), 54-76.
[12]	E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959), 269-271.
[13]	M. C. Dourado, F. Protti and J. L. Szwarcfiter, Complexity results related to monophonic convexity, Discr. Appl. Math. 158 (1268-1274), 2010.
[14]	M. C. Dourado, D. Rautenbach and P. M. Schafer, On finite convexity spaces induced by sets of paths in graphs, Discrete Math. 311 (2011), 616-619.
[15]	G. M. Downs, V. J. Gillet, J. D. Holliday and M. F. Lynch, Review of ring perception algorithms for chemical graphs, J. Chem. Inf. Comput. Sci. 29 (1989), 172-187.
[16]	M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, in: 25th Annual Symposium on Foundations of Computer Science, Computer Society Press, 1984, pp. 338-346.
[17]	P. M. Gleiss, J. Leydold and P. F. Stadler, Interchangeability of relevant cycles in graphs, Electr. J. Comb 7 (2000), #R16.
[18]	R. Hammack, W. Imrich and S. KlavZar, Handbook of Product Graphs, Discrete Mathematics and its Applications, CRC Press, 2nd edition, 2011.
[19]	D. Hartvigsen and R. Mardon, The all-pair min-cut problem and the minimum cycle basis problem on planar graphs, SIAM J. Discr. Math. 7 (1994), 403-418.
[20]	D. Hartvigsen and E. Zemel, Is every cycle basis fundamental?, J. Graph Theory 13 (1989), 117-137.
138
ArsMath. Contemp. 7 (2014) 123-140
[21]	P. Helman, B. M. Mont and H. D. Shapiro, An exact characterization of greedy structures, SIAM J. Discr. Math. 6 (1993), 274-283.
[22]	J. D. Horton, A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987), 359-366.
[23]	W. Imrich and S. KlavZar, Product Graphs. Structure and Recognition, Wiley-Interscience, New York, 2000.
[24]	W. Imrich, S. KlavZar and D. F. Rall, Topics in Graph Theory. Graphs and Their Cartesian Product, A K Peters, Ltd., Wellesley, MA, 2008.
[25]	W. Imrich and P. F. Stadler, Minimal cycle bases of product graphs, Australasian J. Comb. 26 (2002), 233-244.
[26]	P. 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.
[27]	A. Kaveh, Structural Mechanics: Graph and Matrix Methods, Research Studies Press, Exeter, UK, 1992.
[28]	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.
[29]	T. Kavitha, K. Mehlhorn and D. Michail, New approximation algorithms for minimum cycle bases of graphs, Algorithmica 59 (2011), 471-488.
[30]	S. KlavZar and S. Shpectorov, Tribes of cubic partial cubes, Discrete Math. Theor. Comput. Sci. 9 (2007), 273-291.
[31]	S. KlavZar and S. Shpectorov, Convex excess in partial cubes, J. Graph Theory 69 (2012), 356-369.
[32]	K. Klemm and P. F. Stadler, A note on fundamental, non-fundamental, and robust cycle bases., Discr. Appl. Math. 157 (2009), 2432-2438.
[33]	K. A. Lehmann and S. Kottler, Visualizing large and complex networks, in: M. Kaufmann and D. Wagner (eds.), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Springer, Berlin, Heidelberg, volume 4372 of Lect. Notes Comp. Sci., 2007, pp. 240-251.
[34]	S. Lemieux and F. Major, Automated extraction and classification of RNA tertiary structure cyclic motifs, Nucleic Acids Res. 34 (2006), 2340-2346.
[35]	J. Leydold and P. F. Stadler, Minimal cycle basis of outerplanar graphs, Elec. J. Comb. 5 (1998), 209-222, #R16, 14 p.
[36]	C. Liebchen and L. Peeters, Integral cycle bases for cyclic timetabling, Discrete Optimization 6 (2009), 98-109.
[37]	C. Liebchen and R. Rizzi, Classes of cycle bases, Discr. Appl. Math. 155 (2007), 337-355.
[38]	C. Liebchen, G. Wunsch, E. Köhler, A. Reich and R. Rizzi, Benchmarks for strictly fundamental cycle bases, in: Workshop on Experimental and Efficient Algorithms, 2007, pp. 365-378.
M. Hellmuth J. Leydold and P. F. Stadler: Convex cycle bases
139
[39]	H. M. Mulder and L. Nebesky, Axiomatic characterization of the interval function of a graph, Eur. J. Comb. 30 (2009), 1172-1185.
[40]	P.-J. Ostermeier, M. Hellmuth, J. Leydold, K. Klemm and P. F. Stadler, A note on quasi-robust cycle bases, Ars Mathematica Contemporanea 2 (2009), 231-240.
[41]	M. Plotkin, Mathematical basis of ring-finding algorithms in CIDS, J. Chem. Doc. 11 (1971), 60-63.
[42]	E. Sampathkumar, Convex sets in a graph, Indian J. pure appl. Math. 15 (1984), 1065-1071.
[43]	P. F. Stadler, Minimal cycle bases of Halin graphs, J. Graph Theory 43 (2003), 150-155.
[44]	P. Vismara, Union of all the minimum cycle bases of a graph, Electr. J. Comb. 4 (1997), #R9, printed version J. Comb 4 (1997), 73-87.
[45]	P. M. Weichsel, Distance regular subgraphs of a cube, Discrete Mathematics 109 (1992), 297 -306.
[46]	H. Whitney, On abstract properties of linear dependence, Am. J. Math. 57 (1935), 509-533.
[47]	P. M. Winkler, Isometric embedding in products of complete graphs, Discr. Appl. Math. 8 (1984), 209-212.
Appendix A: Modified Dijkstra Algorithm
A shortest path algorithm that keeps track of the multiplicity of shortest paths and keeps some backtracing information is required as a pre-processing step in the computation of convex cycle bases. We use a modified version of Dijkstra's approach [12]. Let ¿(x, y) denote the length of the edge {x, y} in G, dxy — distG(x, y) is the length and Sxy is the number of shortest paths in between x and y, nsx is the predecessor of x along the unique shortest path from s to x, and nsx — 0 otherwise. Q denotes a priority queue sorted by dsx for fixed s.
Input: G — (V, E, /* an edge-weighted graph */ Output: Matrices [Sxy], [dxy], and [nxy]. 1: for all s € V do 2: /* Modified Dijkstra algorithm */ 3: for all v € V do 4: dsv — to; Ssv — 0; nsv — 0
5: dss — 0; Sss — 0; nss — s
6
7
8 9
10 11 12
13
14
15
16
Q ^ V;
while (Q = 0) do
u := vertex with smallest d.
'SU'
if (dsu — to) then
break /* G not connected */
remove u from Q
for all neighbors v € Q n N(u) of u do
t := dsu + ¿(u,v) if (dsv — t) then
Ssv :— Ssv + 1; ns,v — 0 /* more than one shortest path */
if (dsv > t) then
140
ArsMath. Contemp. 7 (2014) 123-140
17:	dsv • t; Ssv • 1; n sv u
The algorithm runs in O(\V\(\E\ + \V| log \V|)) when the min-priority queue Q is implemented by means of a Fibonacci heap [16]. The modifications do not change the asymptotic complexity of the algorithm.