A perihamiltonian is a nonhamiltonian graph for which every edge-contracted subgraph is Hamiltonian.
The numbers of perihamiltonian graphs on 
, 2, ... vertices are 0, 1, 0, 0, 1, 0, 4, 0, 43, 2, 1730,
25, ... (OEIS A392751; House of Graphs), using
the convention that 
is considered Hamiltonian.
See also
Almost Hamiltonian Graph,
Hamiltonian Graph,
Perfectly
Hamiltonian Graph,
Subhamiltonian Graph
Explore with Wolfram|Alpha
References
Fabrici, I.; Madaras, T.; Timková, M.; van Cleemput, N.; and Zamfirescu, C. T. "Non-Hamiltonian Graphs in Which Every Edge-Contracted
Subgraph Is Hamiltonian." Appl. Math. Comput. 392, Art. 125714,
2021.House of Graphs. "Perihamiltonian Graphs." https://houseofgraphs.org/meta-directory/perihamiltonian.Sloane,
N. J. A. Sequence A392751 in "The
On-Line Encyclopedia of Integer Sequences."
Cite this as:
Weisstein, Eric W. "Perihamiltonian Graph."
From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PerihamiltonianGraph.html
