Cubic graph
From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, a cubic graph is a graph where all vertices have degree 3. In other words a cubic graph is a 3-regular graph.
A bicubic graph is a cubic bipartite graph.
In 1880, P.G. Tait conjectured that every cubic graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example, a 46-vertex graph now named for him, in 1946.
In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Horton provided a 96-vertex counterexample.
In 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
- Weisstein, Eric W., et al. "Tait's Hamiltonian Graph Conjecture". Accessed April 23, 2005.
- Weisstein, Eric W., et al. "Bicubic graphs". Accessed April 23, 2005.
- Petr Hliněný. Crossing Number Is Hard for Cubic Graphs. MFCS 2004: 772-782. 2003.
