Cubic graph
Encyclopedia : C : CU : CUB : Cubic graph
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.
See also
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.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.