Cubic graph
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Cubic_graph".

The Petersen graph is a Cubic graph.

A complete cubic bipartate graph is an example of a bicubic graph

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.

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.

See also

• Petersen graph
• Tietze's graph
• Snark
• Utility graph

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.