Distance regular subgraphs of a cube

DOI10.1016/0012-365X(92)90300-5MaRDI QIDQ686314zbMATH OpenOpenAlexFDO

Authors Paul M. Weichsel

Publication date 14 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90300-5

zbMATH Keywords

\(n\)-dimensional cubeCayley graphdistance regular graphsisometric embeddings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Review text

The \(n\)-dimensional cube \(Q_ n\) is regarded as a Cayley graph for the group \((Z_ 2)^ n\) generated by the standard basis. For \(n\) odd, a ``revolving door is the induced subgraph of \(Q_ n\) whose vertices are as evenly balanced in the number of 0's and 1's as possible. It is shown that distance regular graphs with isometric embeddings in cubes are precisely the cubes, the even cycles, and the ``revolving doors. It is also shown that a distance regular graph of girth 4 embedded (not necessarily isometrically) in a cube is itself a cube; some bounds are obtained on various parameters.

Recommendations

• On subgraphs in distance-regular graphs
• Cubical graphs and cubical dimensions
• Distance-regular isometric subgraphs of the halved cubes
• New regular embeddings of n‐cubes Q_n
• Cubic Distance-Regular Graphs

Cites work

• Distance-preserving subgraphs of hypercubes
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Hypermetric Spaces and the Hamming Cone
• On cubical graphs

Cited in

(17)

• \(\ell_ 1\)-rigid graphs
• Weighted efficient domination problem on some perfect graphs
• Distance-regular isometric subgraphs of the halved cubes
• Cubic inflation, mirror graphs, regular maps, and partial cubes
• Distance regularity in direct-product graphs
• Characterization of 2-arc-transitive partial cubes
• Modelling and solving the perfect edge domination problem
• There are no finite partial cubes of girth more than 6 and minimum degree at least 3
• Efficient domination through eigenvalues
• Structure of squares and efficient domination in graph classes
• On middle cube graphs
• On regular subgraphs of augmented cubes
• Some remarks on the square graph of the hypercube
• Hypercube embeddings and Cayley graphs generated by transpositions
• Characterizing graphs with fully positive semidefinite Q-matrices
• A characterization of regular partial cubes whose all convex cycles have the same lengths
• On subgraphs in distance-regular graphs

This page was built for publication: Distance regular subgraphs of a cube

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