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.