TOPICS

# Maximally Nonhamiltonian Graph

A maximally nonhamiltonian graph is a nonhamiltonian graph for which is Hamiltonian for each edge in the graph complement of , i.e., every two nonadjacent vertices are endpoints of a Hamiltonian path.

Since an edge added between two disconnected components of a disconnected graphs is a bridge, and after crossing a bridge in one direction, a Hamiltonian cycle cannot "cross back" in the other, it can be seen that only connected nonhamiltonian graphs can be maximally nonhamiltonian.

The status of the path graph is debatable since it is nonhamiltonian but has empty graph complement, but by a strict interpretation that "all 0 of its complement's edges result in a Hamiltonian graph," it should be considered maximally nonhamiltonian.

The numbers of maximally nonhamiltonian graphs on , 2, ... vertices are 0, 1, 1, 1, 3, 3, 7, 9, 18, 31, ... (OEIS A185306), the first few of which are illustrated above. Larger examples the Coxeter graph, flower snarks for odd , Petersen graph, and Tietze's graph (Clark and Entringer 1983).

Almost Hamiltonian Graph, Hamilton-Connected Graph, Nonhamiltonian Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bollobás, B. Extremal Graph Theory. New York: Academic Press, p. 167, 1978.Bondy, J. A. "Variations on the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.Sloane, N. J. A. Sequence A185306 in "The On-Line Encyclopedia of Integer Sequences."

## Cite this as:

Weisstein, Eric W. "Maximally Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MaximallyNonhamiltonianGraph.html