TOPICS
Search

Doyle Graph


DoyleGraph

The Doyle graph, sometimes also known as the Holt graph (Marušič et al. 2005), is the quartic symmetric graph on 27 nodes illustrated above in several embeddings. It is notable because it is a small graph that is symmetric but not arc-transitive. In other words, any edge of the Doyle graph can be mapped to any other, but in only one of the two possible ways.

Following Alspach et al. (1994), call a vertex-transitive and edge-transitive graph that is not arc-transitive a "1/2-transitive graph." The Doyle graph is in fact the unique smallest 1/2-transitive graph (Alspach et al. 1994). Note that while Holt (1981) mentions that a referee informed him that Kornya found another example with 27 vertices, the Doyle graph is in fact the only l/2-transitive graph with 27 vertices and of degree 4 (Alspach et al. 1994).

Such graphs were first considered by Tutte (1966), who showed that any 1/2-transitive graph must be regular of even degree. The first examples were given by Bouwer (1970), who gave a constructive proof for a connected 2n-regular symmetric arc-intransitive graphs for all integers n>=2. The smallest such Bouwer graph has 54 vertices and is quartic.

Dolye (1976) and subsequently Holt (1981) discovered the graph now known as the Doyle graph. This graph can be obtained from Bouwer's 54-vertex graph by contracting pairs of diametrically opposed vertices (Doyle 1998). It is also a subgraph of the (3,3)-Hamming graph. Several embeddings are illustrated above, the first of which is due to Doyle (1998) and the last due to Marušič et al. (2005).

It is implemented in the Wolfram Language as GraphData["DoyleGraph"].

The graph can be concisely described and constructed from the vertex set {(alpha,beta)|alpha in Z_9,beta in Z_3}, where (alpha,beta) is joined to (4alpha+/-1,beta-1) and (7alpha+/-7,beta+1) (Holt 1981).

DoyleGraphUnitDistance

The Doyle graph is a unit-distance graph. A number of unit-distance embeddings are illustrated above, including edge-vertex degenerate embeddings due to E. Gerbracht (pers. comm., Dec. 27, 2009) and E. Weisstein (Oct. 26, 2023), and a beautiful (and unique) maximally symmetric embedding due to J. Tan (pers. comm., Oct. 16, 2021).

DoyleGraphLCF

The Doyle graph has two distinct LCF notations of order 9 and sixteen of order 3, illustrated above, together with 1818 of order one.

The following table summarized a number of its properties, where alpha, beta, and gamma are the (real) roots of x^3-6x+2 ordered from smallest to largest.


See also

Arc-Transitive Graph, Bouwer Graph, Quartic Graph, Quartic Symmetric Graph

Explore with Wolfram|Alpha

References

Alspach, B.; Marušič, Dragan; and Nowitz, L. (1994), "Constructing Graphs which are 1/2-Transitive." J. Austral. Math. Soc. 56, 391-402, 1994.Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.Doyle, P. G. On Transitive Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. http://arxiv.org/abs/math/0703861.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 37, 2001.Holt, D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J. Graph Th. 5, 201-204, 1981.Marušič, D.; Pisanski, T.; and Wilson, S. "The Genus of the Gray Graph is 7." Europ. J. Combin. 26, 377-385, 2005.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Tan, J. "Of Christmas Lights: the Nine Colourings of the Holt Graph." Dec. 16, 2021. https://community.wolfram.com/groups/-/m/t/2426803.Tutte, W. T. Connectivity in Graphs. Toronto, CA: University of Toronto Press, 1966.

Cite this as:

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

Subject classifications