Cubic graph
From Wikipedia, the free encyclopedia
Not to be confused with graphs of cubic functions.
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.
A bicubic graph is a cubic bipartite graph.
Contents |
[edit] 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.
- 1934: Ronald M. Foster begins collecting examples of cubic symmetric graphs, forming the start of the Foster census.
- 1971: Tutte conjectured that all bicubic graphs are Hamiltonian. However, Horton provided a 96-vertex counterexample.
- 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.
[edit] See also
[edit] References
- 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.
[edit] External links
- Weistein, Eric W., "Bicubic Graph" from MathWorld.
- Weistein, Eric W., "Cubic Graph" from MathWorld.
- Weistein, Eric W., "Tait's Hamiltonian Graph Conjecture" from MathWorld.
