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

Qiang Wang; Liming Xiong

doi:10.1016/j.dam.2025.05.017

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 journal › Article › peer-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 language	English
Pages (from-to)	290-300
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	373
DOIs	https://doi.org/10.1016/j.dam.2025.05.017
Publication status	Published - 15 Oct 2025
Externally published	Yes

Keywords

2-factor
Even-factor
Forbidden pair
Hamiltonian

Access to Document

10.1016/j.dam.2025.05.017

Cite this

@article{a2c31cb894294498b50149895af94329,

title = "Forbidden pairs for 2-factorable and hamiltonian graphs under the necessary condition",

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.",

keywords = "2-factor, Even-factor, Forbidden pair, Hamiltonian",

author = "Qiang Wang and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier B.V.",

year = "2025",

month = oct,

day = "15",

doi = "10.1016/j.dam.2025.05.017",

language = "English",

volume = "373",

pages = "290--300",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

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

AU - Wang, Qiang

AU - Xiong, Liming

PY - 2025/10/15

Y1 - 2025/10/15

N2 - 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.

AB - 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.

KW - 2-factor

KW - Even-factor

KW - Forbidden pair

KW - Hamiltonian

UR - http://www.scopus.com/inward/record.url?scp=105005090658&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2025.05.017

DO - 10.1016/j.dam.2025.05.017

M3 - Article

AN - SCOPUS:105005090658

SN - 0166-218X

VL - 373

SP - 290

EP - 300

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this