Distance-preserving subgraphs of Johnson graphs

DOI10.1007/S00493-016-3421-YMaRDI QIDQ1743174zbMATH OpenOpenAlexFDO

Authors Victor Chepoi

Publication date 12 April 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04047

zbMATH Keywords

Johnson graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: We give a characterization of distance--preserving subgraphs of Johnson graphs, i.e. of graphs which are isometrically embeddable into Johnson graphs (the Johnson graph $J(m,Lambda)$ has the subsets of cardinality $m$ of a set $Lambda$ as the vertex--set and two such sets $A,B$ are adjacent iff $|AriangleB|=2$). Our characterization is similar to the characterization of D. v{Z}. Djokovi'c (J. Combin. Th. Ser. B 14 (1973), 263--267) of distance--preserving subgraphs of hypercubes and provides an explicit description of the wallspace (split system) defining the embedding.

Recommendations

• The Johnson graphs satisfy a distance extension property
• Distance preserving graphs and graph products.
• Induced subgraphs of Johnson graphs
• A local characterization of the Johnson scheme
• Isometric embeddings of Johnson graphs in Grassmann graphs

Cites work

• A canonical decomposition theory for metrics on a finite set
• Combinatorics of lopsided sets
• COMs: complexes of oriented matroids
• Decomposition and \(l_1\)-embedding of weakly median graphs
• Distance-preserving subgraphs of hypercubes
• Isometric embedding in products of complete graphs
• Isometric embeddings in Hamming graphs
• Isometric subgraphs of Hamming graphs and d-convexity
• Lopsided sets and orthant-intersection by convex sets
• Matroid basis graphs. II
• Metric graph theory and geometry: a survey
• On scale embeddings of graphs into hypercubes
• On two conjectures of maurer concerning basis graphs of matroids
• Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube
• The classification of finite connected hypermetric spaces

Cited in

(9)

• On density of subgraphs of halved cubes
• Some results on induced subgraphs of Johnson graphs
• Induced subgraphs of Johnson graphs
• The Johnson graphs satisfy a distance extension property
• Graphs with \(G^p\)-connected medians
• l₁-embeddability of shifted quadrilateral cylinder graphs
• First-order logic axiomatization of metric graph theory
• Labeled sample compression schemes for complexes of oriented matroids
• l₁-embeddability under the edge-gluing operation on some nonbipartite graphs

This page was built for publication: Distance-preserving subgraphs of Johnson graphs

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