In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.
Trivalent graphs arise naturally in topology in several ways. For example, if one considers a graph to be a 1-dimensional CW complex, trivalent graphs are generic in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph.
A bicubic graph is a cubic bipartite graph.
Contents |
History
- 1880: P.G. Tait conjectured that every bridgeless planar cubic graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example, a 46-vertex graph now named for him, in 1946.
- 1932: Ronald M. Foster begins collecting examples of cubic symmetric graphs, forming the start of the Foster census.[1]
- 1971: Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices : the Horton graph.[2] Later, Mark Ellingham constructed two more counterexamples : the Ellingham-Horton graphs.[3][4]
- 2003: Petr Hliněný showed that the problem of finding the crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is NP-hard, despite the fact that they have low degree. There are, however, practical approximation algorithms for finding the crossing number of cubic graphs.[5]
See also
- The cubic symmetric graphs: the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs-Smith graph.
- The snarks: the Tietze's graph, the Blanuša snarks, the flower snark, the double-star snark, the Szekeres snark and the Watkins snark.
- The Gray graph, the smallest semi-symmetric cubic graph, the Ljubljana graph, and the Tutte 12-cage two other semi-symmetric cubic graph.
- The Frucht graph, the smallest cubic graph possessing a single graph automorphism.
- LCF notation for Hamiltonian cubic graphs.
References
- ^ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309-317, 1932.
- ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
- ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
- ^ Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.
- ^ Hliněný, Petr (2006), "Crossing number is hard for cubic graphs", J. Comb. Theory, Ser. B 96 (4): 455–471, doi:, http://kam.mff.cuni.cz/~hlineny/papers/crcubic2-mfcs.pdf.
External links
- Weisstein, Eric W., "Bicubic Graph" from MathWorld.
- Weisstein, Eric W., "Cubic Graph" from MathWorld.
- Weisstein, Eric W., "Tait's Hamiltonian Graph Conjecture" from MathWorld.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
