Affordable Access

Publisher Website

Non-Hamiltonian non-Grinbergian graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
17
Issue
3
Identifiers
DOI: 10.1016/0012-365x(77)90165-0

Abstract

Abstract Settling a question of Tutte and a similar question of Grünbaum and Zaks, we present a 3-valent 3-connected planar graph that has only pentagons and octagons, has 92 (200, respectively) vertices and its longest circuit (path, respectively) contains at most 90 (198, respectively) vertices; moreover, it is shown that the family of all 3-valent 3-connected planar graphs, having n-gons only if n≡ 2 (mod3) (or n≡ 1 (mod3)), has a shortness exponent which is less than one.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Non-hamiltonian bicubic graphs

on Journal of Combinatorial Theor... Jan 01, 1989

A large set of non-Hamiltonian graphs

on Discrete Applied Mathematics Jan 01, 2001

Non-hamiltonian5 4 - toughmaximal planar graphs

on Discrete Mathematics Jan 01, 1995

Better approximations of non-Hamiltonian graphs

on Discrete Applied Mathematics Jan 01, 1998
More articles like this..