TOPICS
Search

Cubic Symmetric Graph


A cubic symmetric graph is a symmetric cubic (i.e., regular of order 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.

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. Condor in August 2006 (Condor).

CubicSymmetricDisconnectedGraphs

The numbers of disconnected cubic symmetric graphs on n=2, 4, 6, 8, ... nodes are 0, 0, 0, 1, ..., 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.

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 embeddings 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 embeddings mainly due to Gerbracht (2008, pers. comm., Dec. 2009-Jan. 2010).


See also

Cage Graph, Cubic Graph, Cubic Vertex-Transitive Graph, Distance-Regular Graph, LCF Notation, 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. 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. "Trivalent (cubic) Symmetric Graphs on Up to 2048 Vertices." http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt.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.Pegg, E. Jr. "Math Games: Cubic Symmetric Graphs." Dec. 30, 2003. http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html.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)." http://school.maths.uwa.edu.au/~gordon/remote/foster/#census.Royle, G. "Browse the Graphs." http://school.maths.uwa.edu.au/~gordon/remote/foster/tables.html.Sloane, N. J. A. Sequences A059282, A075124, and A091430 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 Web Resource. https://mathworld.wolfram.com/CubicSymmetricGraph.html

Subject classifications