TOPICS
Search

Noncayley Graph


NoncayleyGraphs

A noncayley graph is a graph which is not a Cayley graph. All graphs that are not vertex-transitive are noncayley graphs. However, some vertex-transitive graph are noncayley. The numbers of vertex-transitive noncayley graphs on n=1, 2, ... nodes are 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 8, 0, 4, 0, 82, ... (OEIS A006792; McKay and Royle 1990, McKay and Praeger 1994), with the first nonzero case occurring at n=10.

Royle maintains a list of non-Cayley graphs up to 31 vertices and although the values for 27, 28 and 30 vertices have not been independently verified (though an error in the groups can only affect the graphs if somehow a minimal transitive group has been omitted, so errors are unlikely).

A partial list of undirected vertex-transitive graphs that are not Cayley graphs is given in the following table, which extends Holton and Sheehan (1993, p. 292) and Scherphuis (and corrects Scherphuis by omitting the great rhombicuboctahedral graph, which is a Cayley graph).


See also

Cayley Graph, Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

McKay, B. D. and Praeger, C. E. "Vertex-Transitive Graphs Which Are Not Cayley Graphs. I." J. Austral. Math. Soc. Ser. A 56, 53-63, 1994.McKay, B. D. and Royle, G. F. "The Transitive Graphs with at Most 26 Vertices." Ars Combin. 30, 161-176, 1990.Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Scherphuis, J. "Cayley Graphs." http://www.jaapsch.net/puzzles/cayley.htm.Sloane, N. J. A. Sequence A006792/M0009 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Noncayley Graph

Cite this as:

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

Subject classifications