TY - JOUR
T1 - Disconnected forbidden pairs force supereulerian graphs to be hamiltonian
AU - Wang, Qiang
AU - Xiong, Liming
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
PY - 2025/2
Y1 - 2025/2
N2 - A graph is said to be supereulerian if it has a spanning eulerian subgraph, i.e., a spanning connected even subgraph. A graph is called hamiltonian if it contains a spanning cycle. A graph is said to be {R,S}-free if it does not contain R or S as an induced subgraph. Yang et al. characterized all pairs of connected graphs R,S such that every supereulerian {R,S}-free graph is hamiltonian. In this paper, we consider disconnected forbidden graph R,S. We characterize all pairs of disconnected graphs R,S such that every supereulerian {R,S}-free graph of sufficiently large order is hamiltonian. Applying this result, we also characterize all forbidden pairs for the existence of a Hamiltonian cycle in 2-edge connected graphs.
AB - A graph is said to be supereulerian if it has a spanning eulerian subgraph, i.e., a spanning connected even subgraph. A graph is called hamiltonian if it contains a spanning cycle. A graph is said to be {R,S}-free if it does not contain R or S as an induced subgraph. Yang et al. characterized all pairs of connected graphs R,S such that every supereulerian {R,S}-free graph is hamiltonian. In this paper, we consider disconnected forbidden graph R,S. We characterize all pairs of disconnected graphs R,S such that every supereulerian {R,S}-free graph of sufficiently large order is hamiltonian. Applying this result, we also characterize all forbidden pairs for the existence of a Hamiltonian cycle in 2-edge connected graphs.
KW - Disconnected subgraph
KW - Forbidden subgraph
KW - Hamiltonian graphs
KW - Supereulerian graphs
UR - http://www.scopus.com/inward/record.url?scp=85207564703&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2024.114301
DO - 10.1016/j.disc.2024.114301
M3 - Article
AN - SCOPUS:85207564703
SN - 0012-365X
VL - 348
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 2
M1 - 114301
ER -