Abstract
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.
| Original language | English |
|---|---|
| Article number | 114301 |
| Journal | Discrete Mathematics |
| Volume | 348 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Feb 2025 |
Keywords
- Disconnected subgraph
- Forbidden subgraph
- Hamiltonian graphs
- Supereulerian graphs
Fingerprint
Dive into the research topics of 'Disconnected forbidden pairs force supereulerian graphs to be hamiltonian'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver