TOPICS
Search

Doob Graph


DoobGraphs

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^m4^n nodes.

Doob graphs are distance-regular and integral with the same parameters as H(n+2m,4) (Brouwer et al. 1989, p. 262). 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.


See also

Graph Cartesian Product, Hamming Graph, Shrikhande Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 27 and 262, 1989.Doob, M. "On Graph Products and Association Schemes." Utilitas Math. 1, 291-302, 1972.Egawa, Y. "Characterization of H(n,q) by the Parameters." J. Combin. Th., Ser. A 31, 108-125, 1981.Godsil, C. D. "Eigenpolytopes of Distance Regular Graphs." Canad. J. Math. 59, 739-755, 1998.

Referenced on Wolfram|Alpha

Doob Graph

Cite this as:

Weisstein, Eric W. "Doob Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DoobGraph.html

Subject classifications