Subhamiltonian toroidal graphs

被引：1

作者：

McKenzie, Thomas ^{[1
]}

Overbay, Shannon ^{[1
]}

机构：

[1] Gonzaga Univ, Spokane, WA 99258 USA

来源：

AFRIKA MATEMATIKA | 2022年 / 33卷 / 02期

关键词：

Book thickness; Hamiltonian graphs; Genus;

D O I：

10.1007/s13370-022-00997-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The problem of determining whether a graph contains a Hamiltonian cycle is difficult but has been well-studied. A related question asks when is a graph, embeddable on a surface S, a subgraph of a Hamiltonian graph which is also embeddable on S? In particular, if a graph has genus g, is it a subgraph of a Hamiltonian graph of genus g? We answer this question for all complete graphs and complete m-partite graphs of genus 0 and 1.

引用

页数：7

共 8 条

[1] BOOK THICKNESS OF A GRAPH
BERNHART, F
KAINEN, PC
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) : 320 - 331
[2] The pagenumber of toroidal graphs is at most seven
Endo, T
[J]. DISCRETE MATHEMATICS, 1997, 175 (1-3) : 87 - 96
[3] Harary F., 1972, GRAPH THEORY, DOI DOI 10.21236/AD0705364
[4] Kainen P.C., GUGU22503
[5] Ollmann LT, 1973, GRAPH THEORY COMPUT, V8, P459
[6] Overbay S, 2014, J COMBIN MATH COMBIN, V91, P299
[7] Yannakakis M, 1986, PROC 18 ANN ACM S TH
[8] Planar graphs that need four pages
Yannakakis, Mihalis
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 145 : 241 - 263

← 1 →