On the tight span of an antipodal graph

DOI10.1016/S0012-365X(99)00337-4MaRDI QIDQ1978148zbMATH OpenOpenAlexFDO

Authors Oliver Goodman, Vincent Moulton

Publication date 15 September 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00337-4

zbMATH Keywords

\(k\)-dimensional hypercubeantipodal graphCayley graphgraph metricinjective envelopemetric spacepath geodesic spacepolytopal structuretight span

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Review text

The tight span of a finite metric space is essentially the `smallest' path geodesic space into which the metric space embeds isometrically [compare \textit{A. W. M. Dress}, Adv. Math. 53, 321-402 (1984; Zbl 0562.54041)]. In this situation, the tight span is also contractible and has a natural cell structure, so that it lends itself naturally to the study of the Cayley graph of a group. As a first step in this study, the tight span of a metric space which arises from the graph metric of an antipodal graph is considered. In particular, some techniques for the study of the tight span of a graph are developed, which are then applied to antipodal graphs. In this way, the polytopal structure of the tight span for special examples of antipodal graphs (e.g., planar antipodal graphs) is found. It is shown that the tight span of the simplest kind of antipodal graphs, the polygon with \(2k\) edges, is the \(k\)-dimensional hypercube. Finally, with the aid of programs written in Mathematica, computer generated examples of tight spans which were made possible by the techniques developed in this paper are presented for 3- and 4-cube, octahedron, icosahedron, dodecahedron and permutahedron with 24 vertices.

Recommendations

• The tight span of an antipodal metric space. I: combinatorial properties
• The tight span of an antipodal metric space. II: Geometrical properties
• Tight span of path connected subsets of the Manhattan plane
• Optimally fast incremental Manhattan plane embedding and planar tight span construction
• Isometric embeddings of semiregular polyhedra, tilings and their duals in hypercubes and cubic lattices
• scientific article; zbMATH DE number 5499509
• Optimal realizations of two-dimensional, totally-decomposable metrics
• An algorithm for the construction of the tight span of finite subsets of the Manhattan plane
• scientific article; zbMATH DE number 1047529
• Shortcut graphs and groups

Cited in

(15)

• Manhattan orbifolds
• Antipodal metrics and split systems
• A note on the uniqueness of coherent decompositions
• The coherency index
• The tight span of an antipodal metric space. II: Geometrical properties
• An algorithm for the construction of the tight span of finite subsets of the Manhattan plane
• Dimensions of tight spans
• The tight span of an antipodal metric space. I: combinatorial properties
• Injective hulls of certain discrete metric spaces and groups.
• scientific article; zbMATH DE number 5005313 (Why is no real title available?)
• A combinatorial higher-rank hyperbolicity condition
• Integral representation of functions on the circle
• Helly groups
• Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
• On the structure of the tight-span of a totally split-decomposable metric

This page was built for publication: On the tight span of an antipodal graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978148)