TOPICS
Search

Perihamiltonian Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A perihamiltonian graph is a nonhamiltonian graph with at least one edge, for which every edge contraction produces a Hamiltonian graph.

With the convention that the singleton graph K_1 is considered Hamiltonian, the path graph P_2=K_2 is perihamiltonian since its only edge contraction is K_1.

Equivalently, a nonhamiltonian graph G with at least one edge is perihamiltonian iff, for every edge uv of G, at least one of the vertex-deleted graphs G-u or G-v is Hamiltonian. Every hypohamiltonian graph is perihamiltonian, and every perihamiltonian graph is traceable. For every integer n>=2, the complete bipartite graph K_(n,n+1) is perihamiltonian (Fabrici et al. 2021).

The numbers of unlabeled perihamiltonian graphs on n=1, 2, ... vertices are 0, 1, 0, 0, 1, 0, 4, 0, 43, 2, 1730, 25, ... (OEIS A392751; House of Graphs), where the second term counts P_2=K_2.

See also

Almost Hamiltonian Graph, Complete Bipartite Graph, Edge Contraction, Hamiltonian Graph, Hypohamiltonian Graph, Perfectly Hamiltonian Graph, Platypus Graph, Subhamiltonian Graph, Traceable Graph, Vertex Deletion

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

Subject classifications