Disconnected forbidden pairs force supereulerian graphs to be hamiltonian

Qiang Wang, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Article number114301
JournalDiscrete Mathematics
Volume348
Issue number2
DOIs
Publication statusPublished - Feb 2025

Keywords

  • Disconnected subgraph
  • Forbidden subgraph
  • Hamiltonian graphs
  • Supereulerian graphs

Cite this