 TOPICS  # Almost Hamiltonian Graph

There are several definitions of "almost Hamiltonian" in use.

As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on nodes having Hamiltonian number .

As defined by Sanders (1987), a graph with vertices is almost Hamiltonian if every subset of vertices is contained in a circuit, a definition which is similar to that for a maximally nonhamiltonian graph. This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360), the first few of which are illustrated above.

Since a tree has Hamiltonian number , an almost Hamiltonian tree satisfies , giving . Since the 3-path graph is the only tree on three nodes, it is also the only almost Hamiltonian tree.

Hypohamiltonian graphs are almost Hamiltonian. Many (or perhaps even all?) snarks are almost Hamiltonian.

Punnim et al. (2007) showed that the generalized Petersen graph is almost Hamiltonian iff and .

Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). Punnim et al. (2007) proved that a cubic nonhamiltonian graph on vertices is almost Hamiltonian iff it is 2-connected and contains a cycle of length . Examples of 2-connected cubic nonhamiltonian graphs on vertices lacking a -cycle and therefore not almost Hamiltonian are summarized in the following table. graph 14 14-cubic graph 120 30 triangle-replaced Petersen graph 36 36-Zamfirescu graph 50 Georges graph 56 56-Ellingham-Horton graph

Graph Circumference, Hamiltonian Cycle, Hamiltonian Graph, Hamiltonian Number, Hamiltonian Walk, Hypohamiltonian Graph, Maximally Nonhamiltonian Graph

## Explore with Wolfram|Alpha More things to try:

## References

Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Sanders, J. H. "Circuit Preserving Edge Maps II." J. Combin. Th., Ser. B 42, 146-155, 1987.Sloane, N. J. A. Sequence A185360 in "The On-Line Encyclopedia of Integer Sequences."

## Cite this as:

Weisstein, Eric W. "Almost Hamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AlmostHamiltonianGraph.html