IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 48 (2010), 1134
ISSN 2232-2094
RETRACTS OF PRODUCTS OF CHORDAL GRAPHS
Bostjan Bresar Jeremie Chalopin Victor Chepoi Matja KovSe Arnaud Labourel Yann Vaxes
Ljubljana, December 14, 2010
o
c^

CD O CD
00 CSI CSI
Retracts of products of chordal graphs
$H
Bostjan Bresar* Jeremie Chalopin^ Victor Chepoi^ Matjaz Kovse* Arnaud Laboured	Yann Vaxes^
Abstract
In this paper, we characterize the graphs G that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K2}3, k-wheels Wk, and k-wheels minus one spoke W- (k > 4) as induced subgraphs. We also show that these graphs G are exactly the cage-amalgamation graphs introduced by Bresar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
o
1 Introduction
Median graphs constitute one of the most important classes of graphs investigated in metric graph theory and occur in different areas of discrete mathematics, metric geometry, and computer science. Median graphs and related median structures (median algebras and median complexes) have many nice properties and admit numerous characterizations. All median structures are intimately related to hypercubes: median graphs are isometric subgraphs of
CO
hypercubes; in fact, by a classical result of Bandelt [1] they are the retracts of hypercubes into which they embed isometrically. It was also shown by Isbell [23] and van de Vel [31] that every finite median graph G can be obtained by successive applications of gated amalgamations from hypercubes, thus showing that the only prime median graph is the two-vertex complete graph K2 (a graph with at least two vertices is said to be prime if it is neither a Cartesian product nor a gated amalgam of smaller graphs). A related construction of median graphs via convex expansions is given in [25, 26]. Median graphs also have a remarkable algebraic structure, which is induced by the ternary operation on the vertex set that assigns to each triplet of vertices the unique median vertex, and their algebra can be characterized using
'Faculty of Natural Sciences and Mathematics, University of Maribor, Koroska cesta 160, SI-2000 Maribor, Slovenia. Email: {bostjan.bresar, matjaz.kovse}@uni-mb.si
^LIF, Aix-Marseille Universite and CNRS, CMI and Faculte des Sciences de Luminy, Marseille, France.
Email: {jeremie.chalopin,victor.chepoi,arnaud.labourel,yann.vaxes}@lif.univ-mrs.fr ^ 1
CD	1
co
four natural axioms [7, 23] among all discrete ternary algebras. Finally, it was shown in [16, 27] that the cubical complexes derived from median graphs by replacing graphic cubes by solid cubes are exactly the CAT(0) cubical complexes. Thus, due to a result of Gromov [20], median complexes can be characterized as simply connected cubical complexes with triangle-free links of vertices. For more detailed information about median structures, the interested reader can consult the survey [6] and the books [18, 22, 26, 32].
This structure theory of graphs based on two fundamental operations, viz., Cartesian multiplication and gated amalgamation, was further elaborated for more general classes of graphs. Some of the results for median graphs have been extended to quasi-median graphs introduced by Mulder [26] and further studied in [8, 10, 33]: quasi-median graphs are precisely the weakly modular graphs not containing induced K2,3 and K4 — e; they can also be characterized as the retracts of Hamming graphs (Cartesian products of complete graphs) and can be obtained from complete graphs by Cartesian products and gated amalgamations. More recently, Bandelt and Chepoi [3, 4, 5] presented a similar decomposition scheme of weakly median graphs and characterized the prime graphs with respect to this decomposition: the hyperoctahedra and their subgraphs, the 5-wheel W5, and the 2-connected plane triangulations in which all inner vertices have degrees > 6. Using these results and a result of Chastand [13, 14], they further showed that weakly median graphs are the retracts of the Cartesian products of their primes and presented an axiomatic characterization of underlying weakly median algebras. The extensive research on generalizations of median graphs leads to a general framework for the study of classes of graphs, closed for Cartesian products and gated amalgamations, proposed in [9, 13, 14].
In this paper, we continue this line of research and characterize the graphs G which are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs which do not contain K2,3, k-wheels Wk, and k-wheels minus one edge W-(k > 4) as induced subgraphs. We establish that these graphs G are exactly the cage-amalgamation graphs introduced by Bresar and Tepeh Horvat [11], i.e. the graphs which can be obtained via successive gated amalgamations from Cartesian products of chordal graphs;
CO
this solves the open question raised in [11]. Finally, we show that replacing all products of cliques of G by products of "solid" simplices, we will obtain a polyhedral cell complex which, endowed with an intrinsic ^-metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
2 Preliminaries and results
All graphs G = (V, E) occurring here are undirected, connected, and without loops or multiple edges. The distance d(u, v) between two vertices u and v is the length of a shortest (u, v)-path, and the interval I(u, v) between u and v consists of all vertices on shortest (u, v)-paths, that is, of all vertices (metrically) between u and v: I(u,v) = {x & V : d(u,x) + d(x,v) = d(u,v)}. An induced subgraph of G (or the corresponding vertex set A) is called convex if it includes
fi
^ 2
2
o
CSI
00 CSI CSI
00
the interval of G between any pair of its vertices. An induced subgraph H of a graph G is said to be gated if for every vertex x outside H there exists a vertex x' (the gate of x) in H such that each vertex y of H is connected with x by a shortest path passing through the gate x' (i.e., x' & I(x,y)). The smallest convex (or gated, respectively) subgraph containing a given subgraph S is the convex hull (or gated hull, respectively) of S. A graph G = (V, E) is isometrically embeddable into a graph H = (W, F) if there exists a mapping p : V ^ W such
S	that dH (p(u), p(v)) = dG(u, v) for all vertices u,v & V. A retraction p of H is an idempotent
nonexpansive mapping of H into itself, that is, p2 = p : W ^ W with d(p(x), p(y)) < d(x, y) for all x,y & W. The subgraph of H induced by the image of H under p is referred to as a retract of H.
A graph G is a gated amalgam of two graphs Gi and G2 if Gi and G2 are (isomorphic to) two intersecting gated subgraphs of G whose union is all of G. The Cartesian product [22] G = G1D ... □Gn of n graphs G1,... ,Gn has the n-tuples (x1,..., xn) as its vertices (with vertex xi from Gi) and an edge between two vertices x = (x1,..., xn) and y = (y1,..., yn) if and only if, for some i, the vertices xi and yi are adjacent in Gi, and xj = yj for the remaining j = i. Obviously, dG(u, v) = E n=1 dot (ui, vi) for any two vertices u = (u1,..., un) and v = (v1,... ,vn) of G. In regard to a decomposition scheme involving multiplication and amalgamation, a graph with at least two vertices is said to be prime if it is neither a Cartesian product nor a gated amalgam of smaller graphs. For instance, the only prime median graph is the two-vertex complete graph K2 [23, 31] and the prime quasi-median graphs are exactly the complete graphs [8, 23].
A graph G is weakly modular [2, 15] if its distance function d satisfies the following triangle and quadrangle conditions (see Figure 1):
C^
Triangle condition: for any three vertices u,v,w with 1 = d(v,w) < d(u,v) = d(u,w) there exists a common neighbor x of v and w such that d(u,x) = d(u,v) — 1.
Quadrangle condition: for any four vertices u,v,w,z with d(v,z) = d(w,z) = 1 and 2 = d(v, w) < d(u, v) = d(u, w) = d(u, z) — 1, there exists a common neighbor x of v and w such that d(u,x) = d(u,v) — 1.
A weakly median graph is a weakly modular graph in which the vertex x defined in the triangle and quadrangle conditions is always unique. Equivalently, weakly median graphs can be defined as the weakly modular graphs in which each triplet of vertices has a unique quasi-median. Median graphs are the bipartite weakly median graphs and, equivalently, can be defined as the graphs in which each triplet of vertices u, v, w has a unique median vertex, i.e., \I(u,v) n I(u,w) n I(v, w)| = 1. Bridged graphs constitute another important subclass of weakly modular graphs. Recall that a graph is called bridged [17, 29] if it does not contain any isometric cycle of length greater than 3, or alternatively, if the closed neighborhood N[A] = A U {y & V : y is adjacent to some x & A} of every convex set A of G is convex. Chordal graphs constitute the most famous subclass of bridged graphs. A graph is said to be
o
CSI
m
u
a
CD U
chordal if it does not contain induced cycles of length greater than 3. In this paper we will investigate the finite graphs G which are obtained from Cartesian products of chordal graphs
u
CD
CD O CD
w
CO
Figure 1: Triangle and quadrangle conditions
0 o
1
CO ^
CO CO
m
CD
$H
CD
m
u
a
CD U
via gated amalgamations. These graphs have been introduced by Bresar and Tepeh Horvat [11] and called cage-amalgamation graphs. More precisely, the Cartesian products of chordal graphs were called in [11] cages, and the graphs that can be obtained by a sequence of gated amalgamations from cages were called cage-amalgamation graphs. It can be easily shown that cage-amalgamation graphs are weakly modular graphs and that they do not contain induced wheels Wk, and almost-wheels W- (the wheel Wk is a graph obtained by connecting a single vertex - the central vertex - to all vertices of the fc-cycle; the almost wheel W- is the graph obtained from Wk by deleting a spoke (i.e., an edge between the central vertex and a vertex of the fc-cycle), see Figure 2 for examples). It was conjectured in [11] that in fact this list of forbidden subgraphs completely characterizes the cage-amalgamation graphs. The main result of our paper proves this conjecture:
Theorem 1. For a finite graph G = (V,E), the following conditions are equivalent:
(i)	G is a retract of the Cartesian product of chordal graphs;
(ii)	G is a weakly modular graph not containing induced wheels Wk, and almost wheels W- for k > 4;
(iii)	G is a cage-amalgamation graph, i.e., it can be obtained by successive applications of gated amalgamations from Cartesian products of 2-connected chordal graphs and K2's.
The proof of this theorem is provided in the following section. The most difficult part of the proof is the implication (ii)^(iii), which we establish in two steps. First, we show that if G is a weakly modular graph not containing induced K2wheels Wk, and almost wheels W- for fc > 3, then all its primes are 2-connected chordal graphs or a K2. In the second part, using the techniques developed in [3], we show that G can be obtained via gated amalgamations from Cartesian products of prime graphs.
V
V
w
2
u
u
u
u
u
CD
CD O CD
K
2,3
W5
W-
Figure 2: The complete bipartite graph K2,3, the wheel W5, and the almost-wheel W5 .
00
0 o
1
00 ^
CO CO
m
CD
$H
CD
m
Our second result, concerns the geometry of polyhedral complexes derived from cage-amalgamation graphs.
An abstract simplicial complex X is a collection of sets (called simplices) such that a £ X and a' C a implies a' £ X. A cubical complex C is a set of (graph) cubes of any dimensions which is closed under taking subcubes and nonempty intersections. Simplices or cubes of the respective complex are called faces. For a complex K denote by V(K) and E(K) the vertex set and the edge set of K, namely, the set of all 0-dimensional and 1-dimensional faces of K. The pair (V(K),E(K)) is called the (underlying) graph or the 1-skeleton of K and is denoted by G(K). The link of a vertex v in a simplicial complex X, denoted link(v), is the graph consisting of all edges e = xy such that v = x,y and {x, y, v} is a simplex of X.
A simplicial complex X is a flag complex (or a clique complex) if any set of vertices is included in a face of X whenever each pair of its vertices is contained in a face of X. (In the theory of hypergraphs this condition is called conformality.) A flag complex can therefore be recovered by its underlying graph G(X): the complete subgraphs of G(X) are exactly the simplices of X. Conversely, for a graph G one can derive a simplicial complex X(G) by taking all complete subgraphs (simplices) as faces of the complex. Analogously, for a graph G one can also derive a cubical complex C(G) by taking all induced subhypercubes as faces. If G is a median graph, then C(G) consists of all hypercubes which are obtained as Cartesian products of the primes graphs (as we noticed above, they are all two-vertex complete graphs K2). The simplicial complexes arising as clique complexes of bridged graphs were characterized in [16] as simply connected simplicial complexes in which the links of vertices do not contain induced 4- and 5-cycles (these complexes have been rediscovered and investigated by Januszkiewicz and Swiatkowski [24], who called them "systolic complexes" and consider them as simplicial complexes satisfying combinatorial nonpositive curvature property, see the definition below).
In the context of graphs G obtained via Cartesian products and gated amalgamations from prime graphs containing cliques of arbitrary size, it is natural to define on each prime graph Gi its clique complex X(Gi) and to derive a complex H(G) by taking all Hamming subgraphs of G (Cartesian products of complete subgraphs of prime graphs) as faces. We call H(G) the Hamming complex of G. If G is a median graph (or more generally, a triangle-free
U
a
CD U
graph), then the Hamming complex of G coincides with the cubical complex defined before. A geometric realization \K\ of a simplicial or cubical complex K is the polyhedral complex obtained by replacing every face a by a "solid" simplex or "solid" axis-parallel box \a\ of the same dimension such that realization commutes with intersection, that is, \a/\n\a"\ = \a'na"\ for any two faces a' and a//. Then \K\ = (J{\a\ : a & K}. If H is a Hamming complex, then each face t of H is the Cartesian product of simplices t = ai x • • • x ak. This is consistent with the standard definition of the product of two (or more) polytopes given on pp. 9-10 of
CD
CO
the book of Ziegler [34]: given two polytopes P C Mra and Q C Rm, the product of P and Q is the set P x Q = {(x,y) : x & P,y & Q}. P x Q is a polytope of dimension dim(P)+dim(Q), whose nonempty faces are the products of nonempty faces of P and nonempty faces of Q. It is well known (see, for example p.110 of [34]) that the product \a1\ x ••• x \ak\ of solid simplices \a1\,..., \ak\ is a convex polyhedron \t\. With some abuse of language, we will call \t\ a Hamming prism or simply a prism. The geometric realization \H\ of a Hamming complex H is obtained by replacing each cell t = a1 x • • • x ak of H by a "solid" Hamming prism \ t \ = \ ai \ x • • • x \ ak \.
Any geometric realization \H(G) \ of H(G) can be endowed with an intrinsic l2-metric [12], transforming \H(G) \ into a complete geodesic space. Suppose that inside every Hamming prism of \H(G) \ the distance is measured according to the Euclidean l2-metric. The intrinsic l2-metric d2 of \H(G) \ is defined by assuming that the distance between two points x,y & \H(G) \ lying in different Hamming prisms equals to the infimum of the lengths of the paths joining them. Here a path in \H(G) \ from x to y is a sequence P of points x = xo,x1.. .xm-1 ,xm = y such that for each i = 0,.. .,m — 1 there exists a Hamming cell \Ti\ containing xi and xi+1; the length of P is l(P) = £m—1 d(xi,xi+1), where d(xi,xi+1) is computed inside \Ti\ according to the Euclidean l2-metric.
A geodesic triangle A(x1 ,x2, x3) in a geodesic metric space (X, d) consists of three distinct points in X (the vertices of A) and a geodesic between each pair of vertices (the sides of A). A comparison triangle for A(x1 ,x2,x3) is a triangle A(x'1, x'2, x'3) in the Euclidean plane E2 such that dE2(x/i,xj) = d(xi,xj) for i,j & {1,2,3}. A geodesic metric space (X,d) is defined
CO
to be a CAT(0) space [20] if all geodesic triangles A(x1 ,x2,x3) of X satisfy the comparison axiom of Cartan-Alexandrov-Toponogov:
o
CSI
00 CSI CSI
CO
If y is a point on the side of A(x1,x2,x3) with vertices x1 and x2 and y' is the unique point on the line segment [x1,x2] of the comparison triangle A(x'1,x'2,x,3) such that dE2(x'i,y/) = d(xi,y) for i = 1,2, then d(x3,y) < dE2 (x'3,y/).
CAT(0) spaces can be characterized in several natural ways (for a full account of this theory consult the book [12]). A geodesic metric space (X, d) is CAT(0) if and only if any two points of this space can be joined by a unique geodesic. CAT(0) is also equivalent to convexity of the function f : [0,1] ^ X given by f (t) = d(a(t), /3(t)), for any geodesics a and /3 (which is further equivalent to convexity of the neighborhoods of convex sets). This implies that CAT(0) spaces are contractible.
Now, we formulate the second result of this paper:
CD
■ i-H J-H
CD
U
a
CD U
Theorem 2. If G is a cage-amalgamation graph, then any geometric realization |H(G)| of its Hamming complex H(G) equipped with the intrinsic l2-metric d2 is a CAT(0) metric space.
That cliques complexes of chordal graphs lead to CAT(0) polyhedral complexes was already noticed in [16] and [21]; Gromov called them tree-like polyhedra.
CD
3 Proof of Theorem 1
The implication (i)^(ii) is obvious: chordal graphs are weakly modular and do not contain induced K2,3, wheels Wk, and almost wheels W- (fc > 4). Weakly modular graphs are closed by taking Cartesian products. If a Cartesian product of fc graphs Hi,...,Hk contains an induced K2,3, Wk, or W-, then necessarily this graph occurs in one of the factors Hi because these graphs cannot be obtained by proper Cartesian products. As a consequence, Cartesian products H = HiD ••• dHk of chordal graphs do not contain induced K2,3,Wk, and W-. If G is a retract of H = HiD • • • DHk, then G is an isometric subgraph of H and therefore G does not contain induced K2,3,Wk, and W- as well. It remains to notice that triangle and quadrangle conditions are preserved by Cartesian products and retractions, thus G is a weakly modular graph, establishing that (i)^(ii). The implication (iii)^(i) is a particular case of Theorem 1 and Corollary 4 of [4] (the proof of Corollary 4 also follows from a more general result of Chastand [14]). By Theorem 1 of [4] any cage-amalgamation graph G embeds isometrically into the Cartesian product H = HiD • • • DHk of its primes. Corollary 4 of [4] then shows that there exists a retraction from H to G, establishing (iii)^(i).
The proof of the implication (ii)^(iii) is the main contribution of this section. It employs the fact that each finite chordal graph admits a perfect elimination scheme which can be
00
computed by Maximum Cardinality Search algorithm [19, 28, 30]. Running a modification of MCS on the gated hull of a triangle in a graph G satisfying the condition (ii) of Theorem 1, we show that the level subgraphs returned by MCS are all convex subgraphs of G. This allows us to show that the gated hull of each triangle of G is a 2-connected chordal graph,
CO
thus identifying the prime graphs of G. To show that G can be obtained from Cartesian CO	products of 2-connected chordal graphs and edges using successive amalgamations, we adapt
the second part of the proof of Theorem 1 of [3].
A simplicial vertex of a graph G is a vertex v such that its neighborhood N(v) = {u £ V(G) : u is adjacent to v} induces a complete subgraph of G. A Perfect Elimination Ordering (PEO) of a graph G = (V, E) with n vertices is a total ordering vi,... ,vn of its vertices such that each vi is a simplicial vertex in the subgraph Gi induced by the level set Li = {vi,... ,vi}. It is well known (see [19]) that a finite graph G admits a perfect elimination ordering if and only if G is chordal. A PEO of a chordal graph G can be found (in linear time) either using Lexicographic Breadth-First-Search (LexBFS) [28] or Maximum Cardinality Search (MCS) introduced by Tarjan and Yannakakis [30]. MCS algorithm works as follows: the first vertex is chosen arbitrarily, and the (i + 1)-th vertex is the unlabeled vertex that has the largest number of already numbered neighbors, breaking ties arbitrarily. We will denote by a(v) the
o
CSI
I
CSI CSI
CD
$H
CD
U
a
CD U
u
CD
CD O CD
CO
0 o
1
CO ^
CO CO
m
CD
$H
CD
m
Figure 3: Illustration of the proof of Lemma 2
number of v in a total ordering v\,... ,vn, i.e., if a(v) = i, then v = vi. We start with two properties of MCS in chordal graphs.
Lemma 1. Let G be a chordal graph and a an ordering of vertices produced by MCS. If a vertex z belongs to an induced path between two vertices x,y, then a(z) < max{a(x), a(y)}.
Proof. Assume without loss of generality that a(x) < a(y) and let P be an induced path between x and y. Suppose by way of contradiction that P contains a vertex z such that a(z) > a(y) and suppose without loss of generality that z is the vertex of P with the largest index i = a(z). Then among all vertices of P the vertex z was labeled last. Hence z and its neighbors z',z" in P all belong to the subgraph Gi. Since z' and z" are not adjacent, z is not a simplicial vertex of Gi, contradicting the fact that on chordal graphs MCS returns a perfect elimination ordering.	□
A minimal (vertex) separator of a graph G = (V,E) is a subset of vertices K of G such that the subgraph of G induced by V — K contains at least two connected components A and B, and that K is minimal by inclusion with respect to this separating property. Then K necessarily separates any two vertices x £ A and y £ B in the sense that all (x, y)-paths share a vertex with K. It is well-known [19] that any minimal separator K of a chordal graph G induces a complete subgraph of G and, moreover, K separates two vertices x and y such that both x and y are adjacent to all vertices of K.
Lemma 2. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G — K, and let u £ A,v £ V be two vertices that are adjacent to all vertices of K. Let a be an ordering of vertices produced by MCS. If a labels some vertex of A before any vertex of B is labeled, then a labels u before any vertex of B.
Proof. Let ao £ A be the vertex with the smallest index a(a0) among all vertices of A U B. Since A is connected, we can choose P := (a0,a\,... ,ak = u) to be a shortest (and therefore induced) path connecting the vertices ao and u in A. Suppose by the way of contradiction
U
a
CD U
co
that there exists b £ B that was labeled before u, i.e. a(b) < a(u), and let b be the first such vertex with respect to a. Denote by L(x) the set of labeled neighbors of a vertex x at the moment of time when b was labeled. Let K0 := L(b). Since K separates A from b £ B, from the choice of b and our assumption we conclude that K0 C K (see also Figure 3).
We assert that for each vertex ai of P, the inequality a(ai) < a(b) holds. Indeed, let t be an arbitrary vertex in K0 and let Pt := (ao,... ,aj,t) be the path from ao to t, obtained from P by adding t at the end. Since a(u) > a(b) > a(t) by the assumption and a(u) > a(a0) from the choice of a0, by Lemma 1 the path Pt is not induced. Since P is induced, the only possible chords on this path are the chords of the form tai, where 0 < i < k. Let it be the smallest index such that t and ait are adjacent. To avoid induced cycles of length greater than 3 in G, for all j comprised between it + 1 and k, the vertices t and aj must be adjacent as well. Since the subpath (a0,... ,ait, t) of Pt is induced, by Lemma 1 we infer that all vertices of this path must be labeled either before t or before a0, but in either case we have a(aj) < a(b) for all 0 < j < it because a(b) > max{a(t),a(a0)}. Set q = max{it : t £ K0}. As a result, we obtain the following property for the vertices of P: every vertex aj £ {a0,..., aq} was labeled before b, i.e., a(aj) < a(b). On the other hand, all vertices aq+1,... ,ak = u are adjacent to all vertices of K0, i.e., K0 C nj=q+\L(aj). We assert that the inclusions K0 C L(aj), j = q + 1,... ,k, are strict. Since aq £ L(aq+1), this inclusion is indeed strict for aq+1. Let £ > q + 1 be the smallest index for which L(a£) = K0. Then, as L(b) = K0 is a proper subset of L(ag-1), MCS must label ag-1 before b, i.e., a(ag-1) < a(b). Hence ag-1 £ L(ag), a contradiction. This implies, in particular, that the vertices aq+1,... ,ak have been all labeled by MCS before b, i.e., a(aj) < a(b) for q < j < k. The claimed assertion is thus proven. Now, since a k = u, this assertion implies that a(u) < a(b), as desired.	□
C^
For the remainder of this section, let G be a weakly modular graph that does not contain any of K23, Wj, and Wj , k > 4, as an induced subgraph. We will show that G can be obtained by a sequence of gated amalgamations from Cartesian products of chordal graphs. We commence by establishing a number of auxiliary results. A subgraph H of G is said to be A-closed if, for every triangle having two vertices in H, the third vertex belongs to H as well; then the smallest A-closed subgraph containing S is the A-closure of S. In order to check whether a given subgraph of G is convex or gated the following lemma is useful. This essentially coincides with Theorem 7 of [15] and can be proved quite easily by induction.
Lemma 3. A connected subgraph H of a weakly modular graph G is convex if and only if H is locally convex, i.e., for every pair of nonadjacent vertices u,v of H all common neighbors of u and v belong to H whenever at least one common neighbor does. Moreover, a convex subgraph is gated if and only if it is A-closed.
o
CSI
Now we will prove that the gated hull H of each triangle T = {a, b, c} of G is a convex chordal subgraph of G. For this, we perform a (partial) Maximum Cardinality Search a in G starting with a(a) = 1,a(b) = 2,a(c) = 3 until the moment when all yet unlabeled vertices have at most one previously labeled neighbor. Denote by H the subgraph of G induced by
U
CD
U
a
CD U
u
CD
a
CD O CD
Q
CO
0 o
1
CO
£ CO CO
H
H
m
CD
$H
CD
m
vi+1
vi+1
vi+1
Figure 4: Different cases in the proof of Claim 1
all labeled vertices at the end of the procedure, and let Hi be the subgraph of H induced by the first i labeled vertices.
Proposition 1. For any i, Hi is a chordal and convex subgraph of G.
Proof. We proceed by induction on i. Clearly, H1,H2, and H3 are all chordal and convex subgraphs of G. By way of contradiction, assume that for some i > 3, Hi is convex and chordal but Hi+1 = Hi U {vi+1} is not convex. By Lemma 3, Hi+1 is not locally convex. Then there exists u £ V(Hi) such that dHi+1 (u, vi+1) = dc(u,vi+1) = 2 and two vertices x £ V(Hi),v £ V(Hi) which are both adjacent to u and vi+1. Now, we will prove that any vertex in Hi, adjacent to vi+1 is also adjacent to v.
Claim 1. N(vm) n Hi C N(v).
Proof of Claim 1. Let y £ Hi be any neighbor of vi+1 in Hi different from x. From the definition of the labeling a, we know that such a vertex exists. By induction assumption, Hi, is convex, hence x and y are adjacent because they have a common neighbor vi+1 not in Hi. First suppose that the vertices u and y are adjacent. To avoid forbidden W- and W4, the vertex v must be adjacent to x and to y, and we are done. Thus we may assume that u and y are not adjacent. We distinguish two cases.
Case 1: v and x are not adjacent.
If v and y are adjacent, then we obtain a forbidden induced W—. Thus we may further assume that the vertices v and y are not adjacent (see Figure 4, left). By the triangle condition, there exists a common neighbor t of u, v, and y. Since Hi is convex and t £ I(u, y), necessarily t £ V(Hi). To avoid an induced C4 in Hi (which is chordal by the induction hypothesis) formed by vertices u, t, y, x, the vertex t must be adjacent to x since u is not adjacent to y. But this leads to a contradiction, since, as v is not adjacent to x and vi+1 is not adjacent to u, the vertices u,v,vi+1,x,t induce a W— or a W4.
Case 2: v and x are adjacent.
By construction, the graph Hi is 2-connected, thus the vertices u and y can be connected in Hi by an induced path P that avoids x. Since Hi is chordal and the path P is induced, to
U
a
CD U
v
v
v
co
avoid an induced cycle of length > 4 formed by some vertices of P U {x}, the vertex x must be adjacent to all vertices of P. To avoid a forbidden wheel Wk induced by v,vi+1,x and the vertices of P, necessarily v or vi+1 is adjacent to some vertex of P. Since P is induced and Hi is convex, v can be adjacent only with the neighbor u/ of u in P and vi+1 can be adjacent only with the neighbor y/ of y in P. If u' = y/ (see Figure 4, center) or only one of the edges vu/ or vi+1y/ exists, then still we can find there an induced wheel Wk, k > 4. Hence u/ = y/ and v,vi+1 are both adjacent to u/ = y/ (see Figure 4, right). Since the induced path P is arbitrary, we infer that each induced path in Hi between u and y is of length 2, and all common neighbors of u and y are adjacent to both v and vi+1 . As a conclusion, the set K = {z & Hi : u,y & N(z)} is a minimal (by inclusion) (u, y)-separator of the chordal graph Hi, and thus is a clique. Both vertices v and vi+1 are adjacent to all vertices of K. Let A be the connected component of Hi — K containing u, and let B be the connected component of Hi — K containing y. Suppose that the first vertex of A U B labeled by a belongs to A. By Lemma 2, u was labeled before any vertex of B. Let b be the first vertex labeled by a in B. Let L(x) denote the set of labeled vertices at the moment of time when b is labeled. Then L(b) C K. Since, K U {u} C L(v), we obtain a contradiction with the choice of MCS to label b before v. By symmetry of v and vi+1, a similar contradiction is obtained when the first vertex of A U B labeled by a belongs to B. This concludes the proof of the claim.
Now, Claim 1 yields N(vi+1) n Hi C N(v) n Hj,. Since u & Hi is adjacent to v but not to vi+1, we obtain a contradiction with the fact that MCS labels vi+1 before v. Hence Hi+1 is locally convex and, therefore, a convex subgraph of G. It is easy to see that Hi+1 is also chordal. Indeed, since Hi is convex, the neighborhood of vi+1 in Hi induces a complete subgraph, thus vi+1 is a simplicial vertex of Hi+1. On the other hand, by the induction assumption Hi is chordal and therefore the ordering v1,... ,vi returned by MCS is a perfect elimination ordering of Hi. As a consequence, v1,..., vi,vi+1 is a perfect elimination ordering of Hi+1, whence Hi+1 is chordal.	□
fc	Proposition 2. T sgted HuU », T = {„,b,c} » G « the l:horM ^ H.
Proof. From Proposition 1 and the definition of H (H is the last of the subgraphs Hi) we infer that H is a chordal convex subgraph of G. H is A-closed because every vertex in G — H has at most one neighbor in H, and, since H is convex, by Lemma 3, H is a gated subgraph of G. On the other hand, if H = Hk, then for any index i < k, the vertex vi has at least two neighbors in Hi-1, thus vi belongs to the gated hull of Hi-1. Now, if by induction assumption Hi-1 is included in the gated hull of the triangle T = {a, b, c}, then vi belongs to this gated hull as well, whence Hi is contained in the gated hull of T, establishing the induction assertion. This shows that H is contained in the gated hull of T. Hence, H is indeed the gated hull of T.	□
CD
Let uv be an edge in G and, from now on, let H be the gated hull of the graph induced by {u, v} in G. If uv does not belong to a triangle of G, then {u, v} is convex and A-closed, thus
U
a
CD U
u
CD
a
CD O CD
Q
CO
Wa
Wb
\ Uab				Uba
				
\\ I				
				1 /
				
Figure 5: The fibers Wa, Wb of the vertices a,b £ V(H).
0 o
1
CO ^
CO CO
w
CD
$H
CD W
U
a
CD U
{u,v} itself is a gated set of G. In this case, H is isomorphic to K2 and is clearly chordal. If u, v lie in a triangle T , then H coincides with the gated hull of T and can obtained by the (partial) MCS procedure as described above. By Proposition 2, H is chordal as well.
Any gated subset S of G gives rise to a partition Wa (a £ S) of the vertex-set of G; viz., the fiber Wa of a relative to S consists of all vertices x (including a itself) having a as their gate in S. For adjacent vertices a, b of S, let Uab be the set of vertices from Wa which are adjacent to vertices from Wb. Let also Ua = {x £ Wa : 3y £ Wa, xy £ E(G)}. By some abuse of notation, Wa, Ua, and Uab will denote both the sets and the subgraphs induced by these sets. An example is given in Figure 5.
Lemma 4. Each fiber Wa relative to H is gated. There exists an edge between two distinct fibers Wa and Wb if and only if a and b are adjacent.
Proof. To show that Wa is gated, since Wa is connected because I(u, a) c Wa for any u £ Wa, by Lemma 3 it suffices to prove that Wa is locally convex and A-closed. Let x,y £ Wa have a common neighbor z, and, for the purposes of contradiction, suppose that z £ Wa. Hence z £ Wb for some b £ V(H) different from a. Since a (resp. b) is the unique vertex that minimizes the distance from x (resp. z) to H, we infer that d(x, a) = d(z, b) = fc and analogously that d(y,a) = d(z,b) = fc. We claim that a and b are adjacent. Indeed, since z £ Wb, there must be a shortest path from z to a, going through b. Since d(z, b) = fc and d(z, a) = d(x, a) + 1 = fc + 1, we infer d(a, b) < 1 which implies that a and b are adjacent.
By using the quadrangle condition for a,x,y, and z (or, if x and y are adjacent, using the triangle condition for a, x, and y) we conclude that x and y have a common neighbor t such that d(a, t) = fc — 1. Since t £ I(x, a), clearly t £ Wa and thus d(b, t) = fc. Applying the quadrangle condition for b, t, z, and x, we infer that t and z have a common neighbor s such that d(b, s) = fc — 1. It is easy to see that t is not adjacent to z and that s is not adjacent to
b
x and y. Consequently, the vertices x, y, z, s, and t induce a K2,3 if x and y are not adjacent, or a W- otherwise. This leads to a contradiction. Hence Wa is locally convex and A-closed, whence each fiber Wa is gated.
Now suppose that there exists an edge uv with u £ Wa and v £ Wb. Since a is the gate of u in H and b is the gate of v in H, we conclude that d(u, a) + d(a, b) = d(u, b) < 1 + d(v, b) and d(v,b) + d(b,a) = d(v,a) < 1 + d(u,a). From these two inequalities we deduce that d(a, b) = 1.	□
Lemma 5. Let a,b £ V(H) be two adjacent vertices. Then Uab = Ua and Uba = Ub.
Proof. If H has only two vertices, the assertion is trivial. Otherwise, since H is a 2-connected chordal subgraph, there exists a vertex c £ V(H) such that a, b, c form a triangle. We first claim that Uab = Uac. Let x £ Uab. Then there exists y £ Ub that is adjacent to x and clearly d(a,x) = d(b,y). Since c £ Wc, we have d(c,x) = d(c,y) = k > 2, and by the triangle condition there exists a common neighbor z of x and y such that d(c, z) = k — 1. It is easy to see that z £ Wc, which implies that x £ Uac. By symmetry, we infer that Uab = Uac. Now, let x £ Ua. Then x £ Uad for some d £ N(a) n H. Since H is 2-connected and chordal, there exists a sequence of vertices b = c0,c1,... ,cm = d of H such that a, ci, and ci+1 form a triangle for all i = 0,.. .m — 1. By the previous reasoning, this implies that Uab = Uaci = Uad. In particular, x £ Uab, showing that Uab = Ua.	□
By Lemma 4, we infer that any vertex x £ Uab = Ua has exactly one neighbor in Uba = Ub. Indeed, since each fiber Wb is gated there cannot be a vertex not in Wb adjacent to two vertices of Wb. This fact combined with Lemma 5 gives rise to the following natural mapping fab : Ua —> Ub that maps x £ Ua to the neighbor of x in Ub.
CO
Lemma 6. Let a, b be two adjacent vertices of H. Then Ua and Ub are isomorphic subgraphs of G and fab is an isomorphism between the graphs Ua and Ub.
Proof. Let x,y be two adjacent vertices of Ua, and suppose that their neighbors x',y' in Ub CO	are not adjacent. Since Wb is convex, we infer that dWb(x', y') = 2. Let z' £ Wb be a common
neighbor of x' and y'. Since d(y,z') = d(y,x') = 2, by the triangle condition we infer that there exists a common neighbor u of y,x', and z'. Since Wb is A-closed, we conclude that u £ Wb. But then y £ Ua has two neighbors u and y' in Ub, which is impossible.	□
Lemma 7. The subgraphs Ua are gated for all a £ V(H) and are mutually isomorphic. Their union is isomorphic to HOU, where U is any of Ua.
HH
Proof. Since H is connected, from Lemma 6, we immediately infer that the subgraphs Ua are all mutually isomorphic. Since each fiber Wa is gated, to prove that Ua is gated it suffices to show that Ua is locally convex and A-closed in the subgraph Wa.
Let x,y £ Ua be two vertices having a common neighbor z £ Ua and suppose that there is a vertex s £ Wa \ Ua that is adjacent to both x and y but not to z (the case when s is adjacent to z is covered by A-closedness of Ua established below). Let b be a neighbor of a in H and
co
o
CSI
I
u
a
CD U
co
let x', z', y' £ Ub be the neighbors of x, z, y, respectively. By Lemma 6 we conclude that z' is adjacent to x' and y' but x' and y' are not adjacent. Then d(s, x') = d(s, y') = d(s, z') —1 = 2 and by the quadrangle condition we find that x',y' and s have a common neighbor s'. Since Wb is convex, s' £ Ub which in turn implies that s £ Ua, a contradiction. This shows that Ua is locally convex.
Let x,y £ Ua be two adjacent vertices and suppose that there is a vertex s £ Wa \ Ua adjacent to both x and y. Let b be a neighbor of a in H and let x', y' £ Ub be the neighbors of x, y respectively. By Lemma 6, we know that x' is adjacent to y'. Then d(s, x') = d(s, y') = 2 and by the triangle condition we find that x',y' and s have a common neighbor s'. Since N(s) C Ua, it implies that either x' or y' has two neighbors in Ua, a contradiction. This shows that Ua is A-closed. Thus Ua is indeed gated.
The structure of the union of all Ua, a £ V(H), is now completely described. Its vertex set is isomorphic to V(H) x V(U), where U is isomorphic to Ua for any a £ V(H). For any vertices a,c £ V(H) and any x £ Ua, y £ Uc, x is adjacent to y if and only if either a = c and xy £ E(Ua), or a and c are adjacent and y is the unique neighbor of x in Uc. Hence the union of Ua over all a £ V(H) is isomorphic to HDU.	□
o
We collected all results to conclude the proof of the implication (ii)^(iii) of Theorem 1. We proceed by induction on the cardinality of G. First, if H (the gated hull of {u, v} in G) is equal to whole graph G, then G is chordal, hence G is a cage-amalgamation graph. Therefore, we can suppose that H is a proper subgraph of G. Now, suppose that for any a £ V(H), the set Wa coincides with Ua. By Lemma 7, G is isomorphic to HDWa = HDUa, where H is a chordal graph. Since Wa has smaller cardinality than G and since Wa is a weakly modular graph without K2,3, Wk, and W—, k > 4 (as a gated subgraph of G), by induction hypothesis Wa is a cage-amalgamation graph. Since Cartesian products and gated amalgams commute (see also Lemma 3.1 of [11]), G = HDWa is a cage-amalgamation graph as well. Finally, suppose that for some a £ V(H) the set Wa — Ua is nonempty. Since Ua is gated and is a separator of G, we conclude that G is the gated amalgam of Wa and G — (Wa — Ua) along the common gated subgraph Ua. Since both those graphs Wa and G — (Wa — Ua) have smaller cardinality that G, they are cage-amalgamation graphs, and thus so is G. This concludes the proofs of the implication (ii)^(iii) and of Theorem 1.
4 Proof of Theorem 2
The proof uses the decomposition scheme from Theorem 1 and runs in three steps: first we show that a geometric realization of the clique complex of a chordal graph is CAT(0), then we establish that a geometric realization of the Hamming complex of a Cartesian product of chordal graphs is CAT(0) as well, and finally we show that gated amalgams of cage-amalgamation graphs preserve the CAT(0) property of their complexes. The proof employs the following known property of CAT(0) spaces due to Reshetnyak and which is a particular case of Basic Gluing Theorem 11.1 of [12]:
CD ■ i J-H
CD
U
a
CD U
r
Gluing theorem: If (X1,d1) and (X2,d2) are two CAT(0) spaces, Ai is a convex non-empty subset of (Xi, di), i = 1,2, and there exists an isometry p between A1 and A2, then the metric space (X1 U X2,d) obtained by gluing X1 and X2 along the sets A1 and A2 is CAT(0).
The metric space (X1 U X2,d) is obtained by identifying A1 and A2 according to p and d is defined to be d1 on X1, d2 on X2, and d(x,y) = inf{d1(x,a) + d2(a,y) : a & A2 = p(A1)} if x & A1 and y & A2.
It was noticed in Corollary 8.4 of [16] that a geometric realization |X(G) | of the clique complex X(G) of a finite chordal graph G is CAT(0). We recall this short proof here because the proof of Theorem 2 is based on the same principle. We proceed by induction on the number of vertices of G. Let x be a simplicial vertex of G. Then x belongs to the unique maximal by inclusion simplex a of X(G) induced by x and all its neighbors in G. Consequently, IX(G)| can be obtained by gluing |a| and IX'1, where X' is the subcomplex of X spanned by a/ := a — {x} and the maximal simplexes of X(G) distinct from a (in fact, X/ is the clique complex of the chordal graph G/ := G — {x}). Since the gluing is performed along a convex set |a/| of both complexes |a| and X| from the result of Reshetnyak mentioned above we obtain that X(G)| is CAt(o) if and only if a and are CAT(0). Since X/ = X(G/) and the graph G/ is chordal, by the induction assumption X/| is CAT(0), and we are done. In view of perfect elimination schemes of chordal graphs G, X(G)| can be written as a directed union \jn=1 |Xi| where |Xi| = |Xi-1| U ^^ and the simplex ^^ meets |Xi-1| over a single face ^i^ Such simplicial polyhedral complexes have been called by Gromov (p.121 of [21]) tree-like polyhedra and also noticed to be CAT(0).
Now suppose that G is a cage-amalgamation graph whose prime graphs are the chordal graphs G1,..., Gm. Each of these graphs occurs as a gated subgraph of G. Let x be a simplicial vertex of G1. Denote by ax the unique maximal by inclusion simplex of X(G1) induced by x and all its neighbors in G1 and let a'x := ax — {x}. For each vertex a of G1, denote by Wa its fiber in G relative to some copy of the gated subgraph G1. From Lemma 4, each such fiber Wa is gated. From Lemmas 6 and 7 we conclude that the boundaries Ua of these fibers Wa are isomorphic gated subgraphs of G. Denote by H„x and Hax the Hamming complexes of the subgraphs of G induced by the unions |Jaeax Ua and IJaea, Ua. Notice that Ha'x is a subcomplex of HGx and that both Ha'x and HGx are subcomplexes of H(G).
Lemma 8. If p,q are two points of \Ha'x ^ then any geodesic connecting p and q in \Hax | is contained in \Ha>x ^
Proof. Suppose by way of contradiction that such a geodesic j(p, q) contains a point in the set \Hax | — \Ha'x | (see Figure 6 for an illustration). Let n1,... ,nk be the maximal by inclusion Hamming prisms of \Hax | intersected by y(p, q) labeled in order in which they are traversed by y(p, q). Let ni be the facet of ni in \Haxx ^ i.e., ni = ni n \Haxx ^ The intersection of any two consecutive prisms ni and ni+1 is a face Ti of each of them. Let t/ denote the facet of Ti in ni (and nj+1). Let ri & y(p, q) n Ti. The orthogonal projection of each prism ni on its facet nj is a non-expansive map fi. Moreover, each point ri is mapped by fi and fi+1 to the same point rj belonging to t/. As a result, the length of the path Y/(p,q) between p = r'0 and q = r'k
U
a
CD U
u
CD
a
CD O CD
Q
CO
		
		Tk \
"f(P, 9) ^^^^ T2		r2 \
P
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
Figure 6: To the proof of Lemma 8
consisting of line segments connecting the consecutive points p,r[ ,r'2,•••, r'k_ i ,q is at most the length of y(p, q) • Since p,q £ \Ha>x \ and y(p, q) passes via a point of \Hax \ — \Ha>x \, at least one of the orthogonal projections r'ir'i+l must be strictly smaller than the length of Y(ri, ri+i) (the portion of y(p, q) comprised between ri and ri+i), thus Y'(p,q) is strictly shorter than Y(p, q), completing the proof of the lemma.	□
Now, by induction on the number of vertices of G, we will establish that if G is a Cartesian product of chordal graphs Gi, • • •, Gm, then \H(G)\ is CAT(0). This is obviously true if each Gi is a clique. So, suppose without loss of generality that Gi is not a clique. Let x be a simplicial vertex of Gi• From Lemma 8 we know that the subcomplex \Ha>x \ is convex (with respect to the d2-metric) in \Hax \• Let Gi := Gi — {x} and G' := G'i\2G2\3... OGm. By induction assumption, \Hax \ and \H(G')\ are CAT(0) spaces. Since \H(G)\ is obtained by gluing \Hax \ and \H(G')\ along \Ha>x \ and \Ha>x \ is convex in \Hax \, to apply the basic gluing theorem it suffices to show that \Ha'x \ is convex in HG')^ This is obviously true when Gi = a'x• Otherwise, Gi contains a simplicial vertex y £ a'x• Let G'' = Gi — {y} and assume by induction assumption that \Ha>x \ is convex in H^''^^ Therefore, if \Ha>x \ is not convex in \H(Gi)\, then we can find two points p,q £ \Ha/x \ and a geodesic 7(p, q) between p and q in \ H(Gi)\ containing at least one point 2 £ \ H(Gi)\ — \ H(G'')\ = \ HUy\ — \Ha'y\• Then Y(p, q) contains two points p', q' £ \Hay \ such that 2 belongs to the portion y(p', q') of 7(p, q) comprised between p' and q'• Since y(p, q) is a geodesic, necessarily y(p', q') is a geodesic between p' and q'• This however contradicts the convexity of \Ha' \ in \Hay \ established in
U
a
CD U
x
u
CD
CD O CD
CO
0 o
1
CO ^
CO CO
m
CD
$H
CD
m
Figure 7: To the proof of Lemma 9
Lemma 8. This shows that \Ha>x \ is convex in \H(G')\ as well, and therefore we can apply the gluing theorem.
Finally, suppose that a graph G is a gated amalgam of two cage-amalgamation graphs G' and G'' along a gated subgraph G0. Suppose by induction assumption that \H(G')\ and \H(G'')\ are CAT(0) spaces. To use the gluing theorem again, it suffices to show that \H(G0)\ is convex (with respect to the intrinsic d2-metric) in both \H(G')\ and \H(G'')\, say in \H(G')\.
Lemma 9. If G0 is a gated subgraph of a cage-amalgamation graph G', then \H(G0)\ is convex in \H(G')\.
Proof. We proceed by induction on the number of vertices of G'. Since G0 is different from G', there exists a vertex y of G0 that has a neighbor y' £ V(G') \ V(G0). Let H be the gated hull of the edge yy'. Consider the partition of G' into fibers Wa with respect to the vertices a of H. Clearly, the gated subgraph G0 is completely contained in the fiber Wy of y. By Proposition 2, H is either a 2-connected chordal graph or an edge. In both cases, H contains a simplicial vertex x different from y. Denote by ax the unique maximal complete subgraph of H containing x and let a'x = ax — {x}. Let D be the subgraph of G' induced by all vertices not belonging to the fiber Wx. Since x is a simplicial vertex of H, it can be easily seen that D is an isometric (in fact a convex) subgraph of G'. D is a cage-amalgamation graph: its primes are the same as those of G' with the single exception that H is replaced by H — {x}. Moreover, G0 is a gated subgraph of D. Thus, by induction assumption, we can suppose that \H(G0)\ is a convex subcomplex of \H(D)\. Now, suppose by way of contradiction that \H(G0)\ is not convex in \H(G')\. Then there exist two points p,q £ \H(G0)\ such that the geodesic y(p, q) connecting p and q in \H(G')\ does not belong to \H(G0)\. Since \H(G0)\ is convex in \H(D)\, 7(p,q) contains at least one point z not belonging to \H(D)\. Then 7(p,q) necessarily contains two points p',q' £ \Ha/x \ (where \Ha/x \ is defined as before) such that z belongs to the part 7(p', q') of 7(p, q) comprised between the points p' and q'. Since y(p', q') is a part of a geodesic, Y(p',q') is a geodesic itself. If Y(p',q') (and therefore z) is contained
U
a
CD U
in the subcomplex \Hax\ of \H(Wx)\, then we obtain a contradiction with Lemma 8 asserting the convexity of \Ha>x \ in \Hax \. Thus we can suppose that 7(p',q') contains some points (say z itself) in \H(Wx)\ — \Hax\. Then necessarily 7(p',q') contains two points p'',q'' £ \H(Ux)\ such that z belongs to the portion y(p'', q'') between p'' and q''. Again, y(p'', q'') is a geodesic as a part of a larger geodesic. But this means that \H(Ux)\ is not a convex subcomplex of \H(Wx)\, contrary to the fact that Ux is a gated subgraph of a cage-amalgamation graph Wx having less vertices than the graph G'. This contradiction establishes Lemma 9.	□
CD
From Lemma 9 we conclude that \H(Go)\ is convex in \H(G')\ and \H(G'')\, therefore the gated amalgamation of G' and G'' along G0 translates into gluing two CAT(0) spaces \H(G')\ and \H(G'')\ along a convex subspace \H(G0)\, thus \H(G)\ is CAT(0) by the gluing theorem. This concludes the proof of Theorem 2.
00
We conclude the paper with two open questions:
Question 1. Is it true that the graphs G which can be obtained by successive gated amalgams from Cartesian products of bridged graphs are exactly the weakly modular graphs not containing K23, the wheels W4 and W5, and the almost wheels W— for k > 4?
Question 2. Characterize the triangle-square complexes (i.e., the 2-dimensional complexes obtained by taking all graph triangles C3 and squares C4 as faces) of cage-amalgamation graphs. In particular, is it true that those complexes are exactly the simply connected triangle-square complexes whose underlying graphs do not contain K2,3, the wheels Wk, and the almost wheels W— for k > 4? In other words, is it possible to replace the global metric condition of "weak modularity" by a topological condition of "simple connectivity"?
CO
Acknowledgement
This research was supported in part by the French-Slovenian Egide PROTEUS project "Distances, structure and products of graphs". The first and the fourth author are also with the
CO
Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, and were also supported by the Ministry of Science and Technology of Slovenia under the grants J1-2043 and P1-0297. The third author was also supported by the ANR Projet Blanc THEOMATRO.
References
HH
[1]	H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984), 501-510.
m
[2]	H.-J. Bandelt and V. Chepoi, A Helly theorem in weakly modular space, Discrete Math. 126 (1996), 25-39.
m
u
a
CD U
[3] H.-J. Bandelt and V. Chepoi, Decomposition and l1-embedding of weakly median graphs, European J. Combin. 21 (2000), 701-714.
[4]	H.-J. Bandelt and V. Chepoi, The algebra of metric betweenness I: subdirect representation and retracts, European J. Combin. 28 (2007), 1640-1661.
[5]	H.-J. Bandelt and V. Chepoi, The algebra of metric betweenness II: axiomatics of weakly median graphs, European J. Combin. 29 (2008), 676-700.
CD
[6]	H.-J. Bandelt and V. Chepoi, Metric graph theory and geometry: a survey, Surveys on Discrete and Computational Geometry: Twenty Years Later, J.E. Goodman, J. Pach, and R. Pollack (eds), Contemp. Math., 453 (2008), 49-86.
o
[7]	H.-J. Bandelt and J. Hedlikova, Median algebras, Discrete Math. 45 (1983), 1-30.
Q
[8]	H.-J. Bandelt, H.M. Mulder, and E. Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994), 681-703.
CO
[9]	B. Bresar, Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory 23 (2003) 215-225.
[10] B. Bresar, S. Klavzar, and R. Skrekovski, Quasi-median graphs, their generalizations, and tree-like equalities, European J. Combin. 24 (2003), 557-572.

[11]	B. Bresar and A. Tepeh Horvat, Cage-amalgamation graphs, a common generalization of chordal and median graphs, European J. Combin. 30 (2009), 1071-1081.
[12]	M. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature, Springer, Berlin, 1999.
[13]	M. Chastand, Fiber-complemented graphs I: structure and invariant subgraphs, Discrete Math. 226 (2001), 107-141.
(N
CO CO
[15] V. Chepoi, Classifying graphs by means of metric triangles (in Russian), Metody Diskret. Anal. 49 (1989), 75-93.
U
a
CD U
[14] M. Chastand, Fiber-complemented graphs II: retractions and endomorphisms, Discrete Math. 268 (2003), 81-101.
[16]	V. Chepoi, Graphs of some CAT(0) complexes, Adv. Appl. Math. 24 (2000), 125-179.
fc
[17]	M. Farber and R. E. Jamison, On local convexity in graphs, Discrete Math. 66 (1987), 231-247.
[18]	T. Feder, Stable Networks and Product Graphs, Mem. Amer. Math. Soc. 555 (1995).
.CD
[19]	M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
CD
[20]	M. Gromov, Hyperbolic groups, Essays in group theory, Springer, New York, 1987, 75263.
[21]	M. Gromov, CAT(k) -spaces: construction and concentration, Zapiski Nauchnykh Semi-narov POMI, 280 (2001), 101-140.
[22]	W. Imrich and S. KlavZar, Product Graphs: Structure and Recognition, Wiley-Interscience Publication, New York, 2000.
CD
[23]	J.R. Isbell, Median algebra, Trans. Amer. Math. Soc. 260 (1980), 319-362.
[24]	T. Januszkiewicz and J. Swiatkowski, Simplicial nonpositive curvature, Publ. Math. IHES 104 (2006), 1-85.
CD
[25]	H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978), 197-204.
[26]	H.M. Mulder, The Interval Function of a Graph, Math. Centre Tracts 132 (Amsterdam), 1980.
[27]	M. Roller, Poc sets, median algebras and group actions, preprint, University of Southampton, 1998.
[28]	D. Rose, R. Tarjan, and G. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (1976), 266-283.
[29]	V. Soltan and V. Chepoi, Conditions for invariance of set diameter under d-convexification in a graph, Cybernetics 6 (1983), 14-18.
CO
0 o
1
[30]	R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13 (1984), 566-579.
[31]	M. van de Vel, Matching binary convexities, Topology Appl. 16 (1983), 207-235.
[32]	M. van de Vel, Theory of Convex Structures, Elsevier Science Publishers, Amsterdam, 1993.
CO
[33]	E. Wilkeit, The retracts of Hamming graphs, Discrete Math. 102 (1992), 197-218.
[34]	G.M. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1995.
m
CD
fi
CD
m
fi a
CD fi