Hamiltonian cycles in 2-tough 2K2-free graphs

Katsuhiro Ota; Masahiro Sanka

doi:10.1002/jgt.22852

Hamiltonian cycles in 2-tough 2K₂-free graphs

Katsuhiro Ota
, Masahiro Sanka

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

Abstract

A graph (Formula presented.) is called a (Formula presented.) -free graph if it does not contain (Formula presented.) as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

Original language	English
Pages (from-to)	769-781
Number of pages	13
Journal	Journal of Graph Theory
Volume	101
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22852
Publication status	Published - 2022 Dec

Keywords

2-factor
2K-free graph
Hamiltonian cycle
toughness

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.22852

Cite this

@article{197fd0ada70649eabfdab44d8584ae07,

title = "Hamiltonian cycles in 2-tough 2K2-free graphs",

abstract = "A graph (Formula presented.) is called a (Formula presented.) -free graph if it does not contain (Formula presented.) as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.",

keywords = "2-factor, 2K-free graph, Hamiltonian cycle, toughness",

author = "Katsuhiro Ota and Masahiro Sanka",

note = "Publisher Copyright: {\textcopyright} 2022 Wiley Periodicals LLC.",

year = "2022",

month = dec,

doi = "10.1002/jgt.22852",

language = "English",

volume = "101",

pages = "769--781",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Hamiltonian cycles in 2-tough 2K2-free graphs

AU - Ota, Katsuhiro

AU - Sanka, Masahiro

PY - 2022/12

Y1 - 2022/12

N2 - A graph (Formula presented.) is called a (Formula presented.) -free graph if it does not contain (Formula presented.) as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

AB - A graph (Formula presented.) is called a (Formula presented.) -free graph if it does not contain (Formula presented.) as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

KW - 2-factor

KW - 2K-free graph

KW - Hamiltonian cycle

KW - toughness

UR - https://www.scopus.com/pages/publications/85132166652

UR - https://www.scopus.com/pages/publications/85132166652#tab=citedBy

U2 - 10.1002/jgt.22852

DO - 10.1002/jgt.22852

M3 - Article

AN - SCOPUS:85132166652

SN - 0364-9024

VL - 101

SP - 769

EP - 781

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -