Decomposition and l1-embedding of weakly median graphs

Weakly median graphs, being defined by interval conditions and forbidden induced subgraphs, generalize quasi-median graphs as well as pseudo-median graphs. It is shown that finite weakly median graphs can be decomposed with respect to gated amalgamation and Cartesian multiplication into 5-wheels, induced subgraphs of hyperoctahedra (alias cocktail party graphs), and 2-connected bridged graphs not containing K4 or K1,1,3 as an induced subgraph. As a consequence one obtains that every finite weakly median graph is l1-embeddable, that is, it embeds as a metric subspace into some R n equipped with the 1-norm. c ○ 2000 Academic Press In this paper we continue to elaborate on a structure theory of graphs based on two fundamental operations, viz., Cartesian multiplication and gated amalgamation. While Cartesian multiplication is a standard operation, gated amalgamation seems to appear only in the context of median graphs and their generalizations; cf. [4, 6, 8, 23, 27]. An induced subgraph H of a graph G is called 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 ′ ; cf. [18]. G is a gated amalgam of two graphs G1 and G2 if G1 and G2 are (isomorphi