The Relation Between Hamiltonian and 1-Tough Properties of the Cartesian Product Graphs

Louis Kao; Chih wen Weng

doi:10.1007/s00373-021-02292-y

The Relation Between Hamiltonian and 1-Tough Properties of the Cartesian Product Graphs

Louis Kao^*, Chih wen Weng

^*Corresponding author for this work

Department of Applied Mathematics

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

Abstract

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G₁□ G₂ of graphs G₁ and G₂ satisfying that G₁ is traceable and G₂ is connected with a path factor. Let P_n be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) P_n□ H is Hamiltonian; (ii) P_n□ H is 1-tough; and (iii) H has a path factor.

Original language	English
Pages (from-to)	933–943
Number of pages	11
Journal	Graphs and Combinatorics
Volume	37
Issue number	3
DOIs	https://doi.org/10.1007/s00373-021-02292-y
State	Published - May 2021

Keywords

Cartesian product graph
Graph toughness
Hamiltonian graph
Path factor

Access to Document

10.1007/s00373-021-02292-y

Cite this

@article{cc4dbe86664c49dab8f7a044bf002a69,

title = "The Relation Between Hamiltonian and 1-Tough Properties of the Cartesian Product Graphs",

abstract = "The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G1□ G2 of graphs G1 and G2 satisfying that G1 is traceable and G2 is connected with a path factor. Let Pn be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) Pn□ H is Hamiltonian; (ii) Pn□ H is 1-tough; and (iii) H has a path factor.",

keywords = "Cartesian product graph, Graph toughness, Hamiltonian graph, Path factor",

author = "Louis Kao and Weng, {Chih wen}",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.",

year = "2021",

month = may,

doi = "10.1007/s00373-021-02292-y",

language = "English",

volume = "37",

pages = "933–943",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - The Relation Between Hamiltonian and 1-Tough Properties of the Cartesian Product Graphs

AU - Kao, Louis

AU - Weng, Chih wen

PY - 2021/5

Y1 - 2021/5

N2 - The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G1□ G2 of graphs G1 and G2 satisfying that G1 is traceable and G2 is connected with a path factor. Let Pn be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) Pn□ H is Hamiltonian; (ii) Pn□ H is 1-tough; and (iii) H has a path factor.

AB - The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G1□ G2 of graphs G1 and G2 satisfying that G1 is traceable and G2 is connected with a path factor. Let Pn be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) Pn□ H is Hamiltonian; (ii) Pn□ H is 1-tough; and (iii) H has a path factor.

KW - Cartesian product graph

KW - Graph toughness

KW - Hamiltonian graph

KW - Path factor

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

U2 - 10.1007/s00373-021-02292-y

DO - 10.1007/s00373-021-02292-y

M3 - Article

AN - SCOPUS:85102282532

SN - 0911-0119

VL - 37

SP - 933

EP - 943

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

The Relation Between Hamiltonian and 1-Tough Properties of the Cartesian Product Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this