Distance-preserving subgraphs of Johnson graphs

2015/03/13 by Chepoi, Victor · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1503.04047

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,Λ) has the subsets of cardinality m of a set Λ as the vertex--set and two such sets A,B are adjacent iff |A\triangle B|=2). Our characterization is similar to the characterization of D. Ž. Djoković (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.

Cited by

• Hamiltonian connectivity of some base-cobase graphs

Related

• Distance Preserving Graphs
• On Distance Preserving and Sequentially Distance Preserving Graphs
• On Constructing Regular Distance-Preserving Graphs
• Distance preserving graphs and graph products
• Modular Decomposition of Graphs and the Distance Preserving Property