Distance-preserving subgraphs of Johnson graphs

DOI10.1007/s00493-016-3421-yzbMath1399.05058arXiv1503.04047OpenAlexW1933407345MaRDI QIDQ1743174

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

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

Related Items (4)

Graphs with \(G^p\)-connected medians ⋮ \(l_1\)-embeddability of shifted quadrilateral cylinder graphs ⋮ First-order logic axiomatization of metric graph theory ⋮ On density of subgraphs of halved cubes

Cites Work

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

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