TY - JOUR
T1 - Forbidden Pairs of disconnected graphs for traceability and hamiltonicity
AU - Liao, Hongli
AU - Wang, Qiang
AU - Xiong, Liming
AU - Zhang, Zhang
N1 - Publisher Copyright:
© 2025 Elsevier B.V.
PY - 2025/8/15
Y1 - 2025/8/15
N2 - In this paper, we firstly characterize all forbidden pairs {R,S} for graphs with a spanning trail that are traceable and traceable graphs that are hamiltonian. There is no change of forbidden pairs for hamiltonicity if we impose a necessary condition of assumption that the graph is traceable; however, there is some difference of forbidden pairs for traceability if we impose a necessary condition that the graph has a spanning trail: different on two pairs of forbidden subgraphs {K1,3,Z2∪K1},{K1,4,Z1} (where Zi is the graph obtained by identifying a vertex of a K3 with an end-vertex of a Pi+1). As a byproduct, we prove that if G is a connected {K1,4,Z1}-free graph, then every subgraph G[T] induced by a trail T is traceable and every subgraph G[T] induced by a closed trail T is either hamiltonian or K2∨3K1.
AB - In this paper, we firstly characterize all forbidden pairs {R,S} for graphs with a spanning trail that are traceable and traceable graphs that are hamiltonian. There is no change of forbidden pairs for hamiltonicity if we impose a necessary condition of assumption that the graph is traceable; however, there is some difference of forbidden pairs for traceability if we impose a necessary condition that the graph has a spanning trail: different on two pairs of forbidden subgraphs {K1,3,Z2∪K1},{K1,4,Z1} (where Zi is the graph obtained by identifying a vertex of a K3 with an end-vertex of a Pi+1). As a byproduct, we prove that if G is a connected {K1,4,Z1}-free graph, then every subgraph G[T] induced by a trail T is traceable and every subgraph G[T] induced by a closed trail T is either hamiltonian or K2∨3K1.
KW - Hamiltonicity
KW - Spanning trail
KW - Traceability
UR - http://www.scopus.com/inward/record.url?scp=105002121625&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2025.04.002
DO - 10.1016/j.dam.2025.04.002
M3 - Article
AN - SCOPUS:105002121625
SN - 0166-218X
VL - 371
SP - 105
EP - 114
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -