Forbidden Pairs of disconnected graphs for traceability and hamiltonicity

Hongli Liao, Qiang Wang, Liming Xiong*, Zhang Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)105-114
Number of pages10
JournalDiscrete Applied Mathematics
Volume371
DOIs
Publication statusPublished - 15 Aug 2025
Externally publishedYes

Keywords

  • Hamiltonicity
  • Spanning trail
  • Traceability

Cite this