On the Hamiltonicity of 2-Connected Graphs Excluding Certain Triads as Induced Subgraphs

Mostaghim, Zohreh; Emam, Sana

doi:10.22055/jamm.2026.50721.2418

On the Hamiltonicity of 2-Connected Graphs Excluding Certain Triads as Induced Subgraphs

Document Type : Original Paper

Authors

Zohreh Mostaghim

Sana Emam

Iran University of Science and Technology

10.22055/jamm.2026.50721.2418

Abstract

In this paper, we investigate sufficient conditions for Hamiltonicity of 2-connected graphs.
In particular, we show that if a graph G of sufficiently large order is free of certain specified induced
subgraphs, then it is Hamiltonian. Determining whether a graph is Hamiltonian is a challenging problem
in graph theory and is known to be computationally hard. Therefore, studying graphs that exclude particular
structures can serve as a useful tool for identifying sufficient conditions guaranteeing the existence of a
Hamilton cycle. Our main results demonstrate every 2-connected graph is P5-free,K1,4-free, and Z1-free
is Hamiltonian. Moreover, we prove that a 2-connected is Hamiltonian if it contains no induced subgraphs
isomorphic to either P4, K1,4 and B2 or to P4, K1,4 and J2(m). The proofs are based on contradiction
and a detailed analysis of induced subgraphs within the structure of the graph.

Keywords

Hamiltonian graph

R-free

Induced subgraph

Hamiltonian cycle

Subjects