Decomposition and \(l_1\)-embedding of weakly median graphs
type: Item
instance of: scholarly article
title: Decomposition and \(l_1\)-embedding of weakly median graphs
zbMATH Open document ID: 0965.05081
author: Hans-Jürgen Bandelt
author: Victor Chepoi
published in: European Journal of Combinatorics
publication date: 2001-08-02T00:00:00Z
review text: The authors give a structure theory for finite weakly median graphs. They show that each such graph can be obtained by successive applications of gated amalgamations from Cartesian products of members in a short list of certain prime graphs. Furthermore they show that any such graph admits a distance-preserving embedding (\(l_1\)-embedding) into some Euclidean space. There is a scale-2-embedding into some hypercube if and only if the graph does not contain an induced subgraph \(K_{1,1,1,1,2}\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1513381
zbMATH Keywords: weakly median graphs
zbMATH Keywords: gated amalgamations
zbMATH Keywords: prime graphs
zbMATH Keywords: embedding
reviewed by: Wolfgang Kühnel
MaRDI profile type: Publication
full work available at URL: eujc.1999.0377
OpenAlex ID: W2122051188
cites work: On bridged graphs and cop-win graphs
cites work: Q3685588
cites work: Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
cites work: Cellular bipartite graphs
cites work: A canonical decomposition theory for metrics on a finite set
cites work: Pseudo-median graphs: Decomposition via amalgamation and Cartesian multiplication
cites work: Q4873790
cites work: Quasi‐median graphs and algebras
cites work: Dismantling absolute retracts of reflexive graphs
cites work: Q3983321
cites work: Q4034786
cites work: Separation of two convex sets in convexity structures
cites work: Bridged graphs are cop-win graphs: An algorithmic proof
cites work: A dynamic location problem for graphs
cites work: \(\ell_ 1\)-rigid graphs
cites work: Geometry of cuts and metrics
cites work: Distance-preserving subgraphs of hypercubes
cites work: Gated sets in metric spaces
cites work: Connected cutsets of a graph and triangle bases of the cycle space
cites work: On local convexity in graphs
cites work: Median Algebra
cites work: On the null-homotopy of bridged graphs
cites work: Q3890733
cites work: On scale embeddings of graphs into hypercubes
cites work: Conditions for invariance of set diameters under d-convexification in a graph
cites work: Matching binary convexities
cites work: Q3141898
cites work: The retracts of Hamming graphs
DOI: 10.1006/EUJC.1999.0377
Recommended article: Q3642616
Recommended article: On geodesic structures of weakly median graphs. I. Decomposition and octahedral graphs
Recommended article: Pseudo-median graphs: Decomposition via amalgamation and Cartesian multiplication
Recommended article: A poset-based approach to embedding median graphs in hypercubes and lattices
Recommended article: A decomposition approach for the \(p\)-median problem on disconnected graphs
Recommended article: Simultaneous embeddings of graphs as median and antimedian subgraphs
Recommended article: On strongly almost trivial embeddings of graphs
Recommended article: Q3115658
Recommended article: Embedding graphs as isometric medians
Recommended article: A Recursive Embedding Approach to Median Graph Computation
description: scientific article; zbMATH DE number 1513381