TOPICS
Search

Cameron Graph


The 231-Cameron graph is a strongly regular Hamiltonian graph on 231 vertices with parameters (nu,k,lambda,mu)=(231,30,9,3). It is distance-regular with intersection array {30,20;1,3}, but is not distance-transitive. It is named after mathematician Peter J. Cameron (Cameron et al. 1978).

It can be constructed by taking as vertices the (22; 2)=231 unordered pairs from the point set of the Steiner triple system S(3,6,22) and joining two vertices when the pairs are disjoint and their union is contained in a block (Brouwer and van Lint 1984).

It has graph spectrum (-3)^(175)9^(55)20^1, and is therefore an integral graph. It has graph automorphism group order Aut(G)=887040.

It is a Hamiltonian graph.

The 231-Cameron graph is implemented in the Wolfram Language as GraphData["CameronGraph"].

CameronGraphsTwisted

A different set of graphs associated with the name Cameron is the set of cubic planar Hamiltonian graphs having exactly 3 Hamiltonian cycles that were constructed by Kathleen Cameron (Cameron 2001; Knuth 2025, Problem 77). The order-n planar cubic Cameron graph has 8n+2 vertices. The first few are illustrated above.

Since they are cubic and contain exactly 3 Hamiltonian cycles, they are automtatically perfectly Hamiltonian. The n=1 and n=2 cases are Halin graphs. For n>1, the graphs have exactly two graph automorphisms (Knuth 2025).

CameronGraphsLCF

For even n, each of the three Hamiltonian cycles gives a bilaterally symmetric LCF embedding. "Nice" LCF embeddings are shown above for n=1 to 5.

These graphs will be implemented in a future version of the Wolfram Language as GraphData[{"Cameron", n]}.


See also

Distance-Regular Graph, Distance-Transitive Graph, Strongly Regular Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Cameron Graph." http://www.win.tue.nl/~aeb/drg/graphs/Cameron.html.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brouwer, A. E. and van Maldeghem, H. "The Cameron Graph." §10.54 in Strongly Regular Graphs. Cambridge, England: Cambridge University Press, pp. 332-333, 2022.Cameron, K. "Thomason's Algorithm for Finding a Second Hamiltonian Circuit Through a Given Edge in a Cubic Graph Is Exponential on Krawczyk's Graphs." Disc. Math. 235, 69-77, 2001.Cameron, P. J.; Goethals, J.-M.; and Seidel, J. J. "Strongly Regular Graphs having Strongly Regular Subconstituents." J. Alg. 55, 257-280, 1978.DistanceRegular.org. "Cameron Graph." https://www.math.mun.ca/distanceregular/graphs//cameron.html.Knuth, D. E. "Hamiltonian Paths and Cycles." Volume 4, Pre-Fascicle 8A in The Art of Computer Programming. Draft. Aug. 19, 2025. https://www-cs-faculty.stanford.edu/~knuth/fasc8a.ps.gz.

Referenced on Wolfram|Alpha

Cameron Graph

Cite this as:

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

Subject classifications