The Doob graph , also called the Egawa graph,
is the graph given by the graph Cartesian product
of
copies of the Shrikhande
graph with a Hamming graph
(i.e., with the graph
Cartesian product of
copies of the tetrahedral graph
).
therefore has
nodes.
Doob graphs are distance-regular and integral with the same parameters as (Brouwer et al. 1989, p. 262). However,
they are not distance-transitive.
Doob graphs for small
are implemented in the Wolfram Language
as GraphData[{"Doob",
{m, n}}].
Special cases are summarized in the following table, where denotes the Shrikhande graph.