Cubic graph

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, a cubic graph is a graph where all vertices are incident to exactly three edges. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

A bicubic graph is a cubic bipartite graph.

[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 [1].

• 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

• Petersen graph
• Snark

[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.