Some conditions for hamiltonian cycles in 1-tough (K2 ∪ kK1)-free graphs

Katsuhiro Ota; Masahiro Sanka

doi:10.1016/j.disc.2023.113841

Some conditions for hamiltonian cycles in 1-tough (K₂ ∪ kK₁)-free graphs

Katsuhiro Ota, Masahiro Sanka

Department of Mathematics

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

2 Citations (Scopus)

Abstract

Let k≥2 be an integer. We say that a graph G is (K₂∪kK₁)-free if it does not contain K₂∪kK₁ as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2k-connected (K₂∪kK₁)-free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k-connected (K₂∪kK₁)-free graph with minimum degree at least [Formula presented] is hamiltonian or the Petersen graph.

Original language	English
Article number	113841
Journal	Discrete Mathematics
Volume	347
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2023.113841
Publication status	Published - 2024 Mar

Keywords

(K∪kK)-free graph
Hamiltonian cycle
Toughness

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2023.113841

Cite this

@article{a4fc33afcde745d6828c7a11643f8621,

title = "Some conditions for hamiltonian cycles in 1-tough (K2 ∪ kK1)-free graphs",

abstract = "Let k≥2 be an integer. We say that a graph G is (K2∪kK1)-free if it does not contain K2∪kK1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2k-connected (K2∪kK1)-free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k-connected (K2∪kK1)-free graph with minimum degree at least [Formula presented] is hamiltonian or the Petersen graph.",

keywords = "(K∪kK)-free graph, Hamiltonian cycle, Toughness",

author = "Katsuhiro Ota and Masahiro Sanka",

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

year = "2024",

month = mar,

doi = "10.1016/j.disc.2023.113841",

language = "English",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Some conditions for hamiltonian cycles in 1-tough (K2 ∪ kK1)-free graphs

AU - Ota, Katsuhiro

AU - Sanka, Masahiro

PY - 2024/3

Y1 - 2024/3

N2 - Let k≥2 be an integer. We say that a graph G is (K2∪kK1)-free if it does not contain K2∪kK1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2k-connected (K2∪kK1)-free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k-connected (K2∪kK1)-free graph with minimum degree at least [Formula presented] is hamiltonian or the Petersen graph.

AB - Let k≥2 be an integer. We say that a graph G is (K2∪kK1)-free if it does not contain K2∪kK1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2k-connected (K2∪kK1)-free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k-connected (K2∪kK1)-free graph with minimum degree at least [Formula presented] is hamiltonian or the Petersen graph.

KW - (K∪kK)-free graph

KW - Hamiltonian cycle

KW - Toughness

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

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

U2 - 10.1016/j.disc.2023.113841

DO - 10.1016/j.disc.2023.113841

M3 - Article

AN - SCOPUS:85179608919

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

M1 - 113841

ER -

Some conditions for hamiltonian cycles in 1-tough (K₂ ∪ kK₁)-free graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this

Some conditions for hamiltonian cycles in 1-tough (K2 ∪ kK1)-free graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this

Some conditions for hamiltonian cycles in 1-tough (K₂ ∪ kK₁)-free graphs