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 -regular symmetric arc-intransitive graphs for all integers . 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 -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 , where is joined to and (Holt 1981).
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).
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 , , and are the (real) roots of ordered from smallest to largest.