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

^*此作品的通信作者

應用數學系

研究成果: Article › 同行評審

1 引文斯高帕斯（Scopus）

摘要

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.

原文	English
頁（從 - 到）	933–943
頁數	11
期刊	Graphs and Combinatorics
卷	37
發行號	3
DOIs	https://doi.org/10.1007/s00373-021-02292-y
出版狀態	Published - 5月 2021

存取文件

10.1007/s00373-021-02292-y

其它文件與鏈接

Link to publication in Scopus

引用此

@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 - https://www.scopus.com/pages/publications/85102282532

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

摘要

存取文件

其它文件與鏈接

指紋

引用此