Cubic Graph (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
Cubic graphs, also called trivalent graphs, are graphs all of whose nodes have degree 3 (i.e., 3-regular graphs). Cubic graphs on 
nodes exists only for even 
(Harary 1994, p. 15). Not-necessarily-connected cubic graphs on 
, 6, and 8 are illustrated above. An enumeration of cubic graphs on 
nodes for small 
is implemented in the Wolfram Language as GraphData["Cubic",_n_].
A necessary (but not sufficient) criterion for a graph to be cubic is that 
, where 
is the edge count and 
is the vertex count.
The numbers of not-necessarily-connected cubic graphs on 2, 4, 6, ... nodes are 0, 1, 2, 6, 21, 94, 540, 4207, ... (OEIS A005638; Robinson and Wormald 1983). The unique 4-node cubic graph is the complete graph 
(the tetrahedral graph). The two 6-node cubic graphs are the circulant graphs 
(the utility graph) and 
. Three of the six 8-node cubic graphs are the cubical graph and circulant graphs 
and 
.
The connected cubics graphs have been determined by Brinkmann (1996) up to 24 nodes, and the numbers of such graphs for 
, 4, ... are 0, 1, 2, 5, 19, 85, 509, 4060, 41301, ... (OEISA002851). Meringer and Royle independently maintain enumerations of connected cubic graphs.
-cage graphs are cubic. In addition, the following tables gives some named graph that are skeletons of polyhedra.
See also
Barnette's Conjecture, Bicubic Graph, Cage Graph,Cubic Nonplanar Graph, Cubic Symmetric Graph, Cubical Graph, Frucht Graph, Horton Graphs, Quartic Graph, Quasi-Cubic Graph, Quintic Graph, Regular Graph, Tait's Hamiltonian Graph Conjecture, Tutte Conjecture,x y z Embedding
Explore with Wolfram|Alpha
References
Brinkmann, G. "Fast Generation of Cubic Graphs." J. Graph Th. 23, 139-149, 1996.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Meringer, M. "Connected Regular Graphs." http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Robinson, R. W.; Wormald, N. C. "Number of Cubic Graphs." J. Graph. Th. 7, 463-467, 1983.Royle, G. "All Cubic Graphs."http://people.csse.uwa.edu.au/gordon/remote/cubics/.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 177, 1990.Sloane, N. J. A. SequencesA002851/M1521 and A005638/M1656 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc. 43, 459-474, 1947.Tutte, W. T. "A Theory of 3-Connected Graphs."Indag. Math. 23, 441-455, 1961.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Cubic Graph." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CubicGraph.html