Distance-preserving subgraphs of Johnson graphs

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.

No reviews yet.

No comments yet.