Egawa graph

The Doob graph D(m, n), also called the Egawa graph, is the graph given by the graph Cartesian product of m copies of the Shrikhande graph with a Hamming graph H(n, 4) (i.e., with the graph Cartesian product of n copies of the tetrahedral graph K_4). D(m, n) therefore has 16^m 4^n nodes. Doob graphs are distance-regular and integral with the same parameters as H(n + 2m, 4) . However, they are not distance-transitive. Doob graphs for small m, n are implemented in the Wolfram Language as GraphData[{Doob, {m, n}}]. Special cases are summarized in the following table, where S denotes the Shrikhande graph.

graph Cartesian product | Hamming graph | Shrikhande graph