An upper bound on the length of a Hamiltonian walk of a maximal planar graph

Takao Asano; Takao Nishizeki; Takahiro Watanabe

doi:10.1002/jgt.3190040310

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

Takao Asano^*, Takao Nishizeki, Takahiro Watanabe

^*Corresponding author for this work

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

16 Citations (Scopus)

Abstract

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.

Original language	English
Pages (from-to)	315-336
Number of pages	22
Journal	Journal of Graph Theory
Volume	4
Issue number	3
DOIs	https://doi.org/10.1002/jgt.3190040310
Publication status	Published - 1980
Externally published	Yes

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.3190040310

Cite this

@article{d4c43f84e9f94a1fb8d183185228a1af,

title = "An upper bound on the length of a Hamiltonian walk of a maximal planar graph",

abstract = "A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.",

author = "Takao Asano and Takao Nishizeki and Takahiro Watanabe",

year = "1980",

doi = "10.1002/jgt.3190040310",

language = "English",

volume = "4",

pages = "315--336",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - An upper bound on the length of a Hamiltonian walk of a maximal planar graph

AU - Asano, Takao

AU - Nishizeki, Takao

AU - Watanabe, Takahiro

PY - 1980

Y1 - 1980

N2 - A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.

AB - A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.

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

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

U2 - 10.1002/jgt.3190040310

DO - 10.1002/jgt.3190040310

M3 - Article

AN - SCOPUS:84986529723

SN - 0364-9024

VL - 4

SP - 315

EP - 336

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this