Distance-preserving subgraphs of Johnson graphs

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 $|A△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.

arXiv comment13 pages, 1 figure