TOPICS
Search

Cubic Symmetric Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A cubic symmetric graph is a regular graph that is both vertex-transitive and edge-transitive and has vertex degree 3. 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.

A connected cubic symmetric 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).

Bouwer et al. (1988) published data for all connected cubic symmetric graphs on up to 512 vertices. Conder and Dobcsányi (2002) found all 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 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.

CubicSymmetricDisconnectedGraphs

The numbers of disconnected cubic symmetric graphs on n=2, 4, 6, 8, ... nodes are 0, 0, 0, 1, 0, 2, 0, 2, 1, 2, 0, 3, 0, 2, 2, 3, 0, 3, 0, 5, 2, 1, 0, 5, ... (OEIS A385181), the smallest of which are illustrated above.

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.

The numbers of connected cubic symmetric graphs on n=2, 4, ... nodes are 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, ... (OEIS A059282). All cubic symmetric graphs having up to 60 nodes are Hamiltonian, with the exception of the Petersen graph (10 nodes) and the Coxeter graph (28 nodes), 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 graphyes[-2]^4
6AK_(3,3) (utility graph)yes[3,-3]^3
8Acubical graphyes[3,-3]^4
10APetersen graphno--
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)Ayes[-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).

Foster 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.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.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, and A385181 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