Forbidden pairs for 2-factorable and hamiltonian graphs under the necessary condition

Qiang Wang, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In [1], Wang and Xiong characterize all forbidden pairs (not necessary connected) R,S such that 2-connected {R,S}-free graph G admitting a 2-factor is hamiltonian. To be more comprehensive, in this paper, we characterize all forbidden pairs (not necessary connected) R,S such that connected (or 2-edge-connected) {R,S}-free graph G admitting a 2-factor is hamiltonian. Besides, we characterize all forbidden pairs (not necessary connected) R,S such that connected (or 2-edge-connected) {R,S}-free graph G admitting an even-factor has a 2-factor. Comparing with the main result of Yang and Xiong (2023), we give all disconnected forbidden pairs. In the end, we find all forbidden pairs R,S such that connected (or 2-edge-connected) {R,S}-free graph G who has an even-factor is hamiltonian.

Original languageEnglish
Pages (from-to)290-300
Number of pages11
JournalDiscrete Applied Mathematics
Volume373
DOIs
Publication statusPublished - 15 Oct 2025
Externally publishedYes

Keywords

  • 2-factor
  • Even-factor
  • Forbidden pair
  • Hamiltonian

Cite this