TOPICS
Search

Cubic Symmetric Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Following the vertex-and-edge-transitive convention, a cubic symmetric graph is a regular graph of vertex degree 3 that is both vertex-transitive and edge-transitive. Such graphs were first studied by Foster (1932). They have since been the subject of much interest and study. Since cubic graphs must have an even number of vertices, so must cubic symmetric graphs.

Bouwer et al. (1988) published data for all connected cubic symmetric graphs on up to 512 vertices. Conder and Dobcsányi (2002) found all connected cubic symmetric graphs up to 768 vertices. Royle maintains a list of known cubic symmetric graphs with fewer than 1000 vertices. (This list is known to be complete for up to 768 vertices, but includes only the Cayley graphs for 770-998 vertices.) All connected cubic symmetric graphs up to 2048 vertices were subsequently enumerated by M. Conder in August 2006 (Conder).

The complete census of Potočnik et al. (2013) contains all 482 connected cubic symmetric graphs on at most 1280 vertices. Conder and Potočnik (2026) enumerated all 3815 connected cubic symmetric graphs on at most 10000 vertices.

CubicSymmetricDisconnectedGraphs

Some of the smallest disconnected cubic symmetric graphs are illustrated above. The following table gives the numbers of nonisomorphic cubic symmetric graphs on 2n vertices for n=1, 2, ..., with separate counts for the connected and disconnected subclasses.

graphsOEIScounts
allA3981790, 1, 1, 2, 1, 2, 1, 3, 2, 4, 0, 4, 1, 3, 3, 4, 0, 3, 1, 6, 3, 1, 0, 6, ...
connectedA0592820, 1, 1, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, ...
disconnectedA3851810, 0, 0, 1, 0, 2, 0, 2, 1, 2, 0, 3, 0, 2, 2, 3, 0, 3, 0, 5, 2, 1, 0, 5, ...
CubicSymmetricGraphs

Connected cubic symmetric graphs on 102 or fewer nodes are illustrated above, denoted F_nZ, where F commemorates Foster, n is the number of vertices, and a letter A, B, C, etc. is appended to indicate the first, second, etc. such graph on n vertices (Royle).

Many connected cubic symmetric graphs, including F_(024)A, F_(060)A, and F_(064)A are Cayley graphs. F_(024)A is isomorphic to the generalized Petersen graph GP(12,5) and was constructed by Foster (1932), Coxeter (1950), and Frucht (1952). The "apparently new symmetrical graph with 64 vertices and girth 8" discussed by Frucht (1952) is F_(064)A. F_(120)B is the rolling polyhedron graph of the regular icosahedron.

All connected cubic symmetric graphs having up to 10000 nodes are Hamiltonian, with the exception of the Petersen graph (10 nodes) and the Coxeter graph (28 nodes) (Conder and Potočnik 2026), so the numbers of Hamiltonian connected cubic symmetric graphs are therefore 0, 1, 1, 1, 0, 0, 1, 1, 1, 2, 0, 1, 1, ... (OEIS A091430). The first few orders of connected cubic symmetric graphs are 4, 6, 8, 10, 14, 16, 18, 20, 20, 24, 26, 28, 30, 32, 38, 40, ... (OEIS A075124).

The smallest number of vertices for which n nonisomorphic connected cubic symmetric graphs exist for n=0, 1, ... are given by 2, 4, 20, 56, 182, 432, 168, 364, 1792, 816, 1024, 1344, 1296, 1536, 6840, ... (OEIS A385173).

Connected cubic symmetric graphs on 102 or fewer nodes are summarized in the table below. In this table, H stands for Hamiltonian and * indicates a graph having no LCF notation of order >1.

FgraphHamiltonianLCF notation
4Atetrahedral graph K_4yes[-2]^4
6AK_(3,3) (utility graph K_(3,3))yes[3,-3]^3
8Acubical graph Q_3yes[3,-3]^4
10APetersen graph Pno--
14AHeawood graphyes[5,-5]^7
16AMoebius-Kantor graphyes[5,-5]^8
18APappus graphyes[5,7,-7,7,-7,-5]^3
20Adodecahedral graphyes[10,7,4,-4,-7,10,-4,7,-7,4]^2
20BDesargues graphyes[5,-5,9,-9]^5
24ANauru graphyes[5,-9,7,-7,9,-5]^4
26AF_(26)Ayes[7,-7]^(13)
28ACoxeter graphno--
30ATutte 8-cageyes[-13,-9,7,-7,9,13]^5
32ADyck graphyes[5,-5,13,-13]^8
38AF_(38)Ayes[15,-15]^(19)
40AF_(40)Ayes[15,9,-9,-15]^(10)
42AF_(42)Ayes[9,-9]^(21)
48AF_(48)Ayes[-7,9,19,-19,-9,7]^8
50AF_(50)Ayes[-21,-19,19,-19,19,-19,19,21,-21,21]^5
54AF_(54)Ayes[-13,-11,11,-11,11,13]^9
56AF_(56)Ayes[-13,-11,11,13]^(14)
56BF_(56)Byes[-28,-19,-12,-18,12,15,-15,-12,18,12,19,-28,-18,18]^4
56CF_(56)Cyes*
60AF_(60)Ayes[12,-17,-12,25,17,-26,-9,9,-25,26]^6
62AF_(62)Ayes[11,-11]^(31)
64AF_(64)Ayes[23,-11,-29,25,-25,29,11,-23]^8
72AF_(72)Ayes[-31,9,-5,5,-9,31]^(12)
74AF_(74)Ayes[-21,21]^(37)
78AF_(78)Ayes[-33,33]^(39)
80AF_(80)Ayes[-25,9,-9,25]^(20)
84AF_(84)Ayes*
86AF_(86)Ayes[-13,13]^(43)
90AFoster graphyes[17,-9,37,-37,9,-17]^(15)
96AF_(96)Ayes[-41,-39,39,41,-41,41,-41,41]^(12)
96BF_(96)Byes[-45,-33,-15,45,-39,-21,-45,39,21,45,-15,15,-45,39,-39,45,33,27,-45,15,-27,45,-39,39]^4
98AF_(98)Ayes[-37,37]^(49)
98BF_(98)Byes[-43,-41,41,-41,41,-41,41,-41,41,-41,41,43,-43,43]^7
102ABiggs-Smith graphyes*
SymmetricCubicGraphsAlternateEmbeddings

The plots above show some alternate drawings for selected cubic symmetric graphs.

UnitDistanceCubicSymmetric

Many cubic symmetric graphs (excepting the tetrahedral graph, utility graph, and possibly others) have unit-distance embeddings, as illustrated above in drawings mainly due to Gerbracht (2008, pers. comm., Dec. 2009-Jan. 2010).

CubicSymmetricGraphTorusEmbeddings

Many (but not all) cubic symmetric graphs are toroidal. These include the utility graph K_(3,3), Petersen graph P, Heawood graph, Möbius-Kantor graph, Pappus graph, Nauru graph, F026A, Dyck graph, F038A, F042A, F050A, F054A, F056A, F062A, F072A, F074A, F078A, F086A, F096A, F098A, F098B, F104A, F114A, F122A, F126A, F128A, F134A, F146A, F150A, F152A, F158A, F162A, F168A, F182A, F182B, F186A, F194A, F200A, F206A, F216A, F218A, F222A, F224A, F234A, F242A, F248A, F254A, F258A, F266A, F266B, F278A, F288A, F294A, F294B, F296A, F302A, F312A, F314A, F326A, F338A, F338B, F342A, F344A, F350A, F362A, F366A, F378A, F384A, F386A, F392A, F392B, F398A, F402A, F416A, F422A, F434A, F434B, F438A, F446A, F450A, F456A, F458A, F474A, F482A, F486A, F488A, F494A, F494B, F504A, F512A, F518A, F518B, F536A, F542A, F546A, F546B, F554A, F558A, F566A, F578A, F582A, F584A, F600B, F602A, F602B, F608A, F614A, F618A, F626A, F632A, F648A, F650A, F654A, F662A, F666A, F672B, F674A, F686A, F686C, F698A, F702B, F722A, F722B, F726A, F728A, F728B, F734A, F744B, F746A, F758A, F762A, F774A, F776A, F794A, F798A, F798B, F800A, F806A, F806B, F818A, F824A, F834A, F842A, F854A, F854B, F864A, F866A, F872A, F878A, F882A, F882B, F888B, F896A, F906A, F914A, F926A, F936B, F938A, F938B, F942A, F950A, F962A, F962B, F968A, F974A, F978A, F992A, and F998A. Torus embeddings for a number of these are illustrated above.

A connected cubic graph G is a 1-arc-regular graph iff its line graph L(G) is a quartic half-arc-transitive graph (Marušič and Xu 1997). The following table gives five examples, where the second column gives the name in the census of Potočnik et al. (2015).

cubic symmetric graph Gcensus name of L(G)
F_(026)AHAT[39,1]
F_(038)AHAT[57,1]
F_(042)AHAT[63,2]
F_(056)AHAT[84,1]
F_(062)AHAT[93,1]

Many cubic symmetric graphs are graph distance graphs of other cubic symmetric graphs. The following table summarizes cubic symmetric graphs that are their own graph distance-k graph.

kgraph is isomorphic to its own graph distance-k graph
7F_(080)A
9F_(112)B, F_(220)C, F_(240)A, F_(256)D
11F_(192)A, F_(336)E, F_(336)F, F_(364)G, F_(432)D, F_(512)E, F_(680)A, F_(728)D
13F_(728)G, F_(744)A, F_(768)F, F_(896)E
17F_(960)B

The following table summarizes cubic symmetric graphs that are graph distance-k graphs of other cubic symmetric graphs.

kgraphgraph distance-k graph
10F_(504)CF_(504)E
11F_(720)DF_(720)F
12F_(364)DF_(364)C

See also

Cage Graph, Cubic Graph, Cubic Vertex-Transitive Graph, Distance-Regular Graph, Foster Graph, Half-Arc-Transitive Graph, LCF Notation, Line Graph, Quartic Symmetric Graph, Quintic Symmetric Graph, Symmetric Graph

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 147, 1993.Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; and Star, Z. The Foster Census. Charles Babbage Research Centre, 1988.Conder, M. "Trivalent (Cubic) Symmetric Graphs on up to 2048 Vertices." https://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt.Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.Conder, M. and Lorimer, P. "Automorphism Groups of Symmetric Graphs of Valency 3." J. Combin. Th. Ser. B 47, 60-72, 1989.Conder, M. and Nedela, R. "Symmetric Cubic Graphs of Small Girth." J. Combin. Th. Ser. B 97, 757-768, 2007.Conder, M. and Potočnik, P. "Census of Cubic Edge-Transitive Graphs." https://fostercensus.graphsym.net.Conder, M. and Potočnik, P. "Edge-Transitive Cubic Graphs: Analysis, Cataloguing and Enumeration." J. Algebra 685, 703-737, 2026. https://doi.org/10.1016/j.jalgebra.2025.07.035.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Coxeter, H. S. M.; Frucht, R.; and Powers, D. L. Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. New York: Academic Press, 1981.Foster, R. M. "Geometrical Circuits of Electrical Networks." Trans. Amer. Inst. Elec. Engin. 51, 309-317, 1932.Frucht, R. "A One-Regular Graph of Degree Three." Canad. J. Math. 4, 240-247, 1952.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 171-175, 1994.House of Graphs. Cubic Symmetric Graphs. Tetrahedron K_4, Utility Graph K_, The cube Q_3, Petersen Graph, Heawood Graph, and others.Marušič, D. and Xu, M. Y. "A 1/2-Transitive Graph of Valency 4 with a Nonsolvable Group of Automorphisms." J. Graph Th. 25, 133-138, 1997. https://doi.org/10.1002/(SICI)1097-0118(199706)25:2%3C133::AID-JGT5%3E3.0.CO;2-N.Pegg, E. Jr. "Math Games: Cubic Symmetric Graphs." Dec. 29, 2003. https://www.mathpuzzle.com/MAA/10-Cubic%20Symmetric%20Graphs/mathgames_12_29_03.html.Potočnik, P.; Spiga, P.; and Verret, G. "Cubic Vertex-Transitive Graphs on up to 1280 Vertices." J. Symb. Comput. 50, 465-477, 2013. https://doi.org/10.1016/j.jsc.2012.09.002.Potočnik, P.; Spiga, P.; and Verret, G. "A Census of 4-Valent Half-Arc-Transitive Graphs and Arc-Transitive Digraphs of Valence Two." Ars Math. Contemp. 8, 133-148, 2015. https://doi.org/10.26493/1855-3974.559.c6c.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Royle, G. "Cubic Symmetric Graphs (the Foster Census)." https://web.archive.org/web/20081004205049/http://people.csse.uwa.edu.au/gordon/remote/foster/#census.Royle, G. "Browse the Graphs." https://web.archive.org/web/20081004205049/http://people.csse.uwa.edu.au/gordon/remote/foster/tables.html.Sloane, N. J. A. Sequences A059282, A075124, A091430, A385173, A385181, and A398179 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

Referenced on Wolfram|Alpha

Cubic Symmetric Graph

Cite this as:

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

Subject classifications