Polyhedra without cubic vertices are prism-hamiltonian

被引：1

作者：

Spacapan, Simon ^{[1
,2
]}

机构：

[1] Univ Maribor, Fac Mech Engn FME, Dept Math, Smetanova 17, Maribor 2000, Slovenia

[2] IMFM, Ljubljana, Slovenia

来源：

JOURNAL OF GRAPH THEORY | 2024年 / 106卷 / 02期

关键词：

circuit graph; Hamiltonian cycle;

D O I：

10.1002/jgt.23078

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The prism over a graph G $G$ is the Cartesian product of G $G$ with the complete graph on two vertices. A graph G $G$ is prism-hamiltonian if the prism over G $G$ is hamiltonian. We prove that every polyhedral graph (i.e., 3-connected planar graph) of minimum degree at least four is prism-hamiltonian.

引用

页码：380 / 406

页数：27

共 24 条

[1] TREES IN POLYHEDRAL GRAPHS
BARNETTE, D
[J]. CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (04): : 731 - &
[2] Barnette D., 1970, J COMBINATORIAL THEO, V9, P54
[3] Prism-hamiltonicity of triangulations
Biebighauser, Daniel R.
Ellingham, M. N.
[J]. JOURNAL OF GRAPH THEORY, 2008, 57 (03) : 181 - 197
[4] Brinkmann G, 2019, ELECTRON J COMB, V26
[5] Hamiltonian decompositions of prisms over cubic graphs
Cada, R
Kaiser, T
Rosenfeld, M
Ryjácek, Z
[J]. DISCRETE MATHEMATICS, 2004, 286 (1-2) : 45 - 56
[6] Dirac G. A., 1952, P LOND MATH SOC, V3, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[7] Toughness and prism-hamiltonicity of P4-free graphs
Ellingham, M. N.
Nowbandegani, Pouria Salehi
Shan, Songling
[J]. DISCRETE APPLIED MATHEMATICS, 2020, 284 : 201 - 206
[8] Hamiltonicity of planar graphs with a forbidden minor
Ellingham, M. N.
Marshall, Emily A.
Ozeki, Kenta
Tsuchiya, Shoichi
[J]. JOURNAL OF GRAPH THEORY, 2019, 90 (04) : 459 - 483
[9] 2-WALKS IN-CIRCUIT GRAPHS
GAO, ZC
RICHTER, RB
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (02) : 259 - 267
[10] On 3-polytopes with non-Hamiltonian prisms
Ikegami, Daiki
Maezawa, Shun-ichi
Zamfirescu, Carol T.
[J]. JOURNAL OF GRAPH THEORY, 2021, 97 (04) : 569 - 577

← 1 2 3 →