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 language | English |
|---|---|
| Pages (from-to) | 105-114 |
| Number of pages | 10 |
| Journal | Discrete Applied Mathematics |
| Volume | 371 |
| DOIs | |
| Publication status | Published - 15 Aug 2025 |
| Externally published | Yes |
Keywords
- Hamiltonicity
- Spanning trail
- Traceability
Fingerprint
Dive into the research topics of 'Forbidden Pairs of disconnected graphs for traceability and hamiltonicity'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver