A nonhamiltonian five-regular multitriangular polyhedral graph
type: Item
instance of: scholarly article
title: A nonhamiltonian five-regular multitriangular polyhedral graph
zbMATH Open document ID: 0854.05065
DOI: 10.1016/0012-365X(95)00203-9
published in: Discrete Mathematics
publication date: 1997-01-05T00:00:00Z
review text: Let \(G\) be a polyhedral graph, i.e. \(G\) is planar and 3-connected. Then \(G\) is called multitriangular if each face of \(G\) is a \(q\)-gon for some \(q\) divisible by 3. In the present paper, the author constructs a 5-regular multitriangular graph with 1728 vertices which does not contain a Hamiltonian cycle. Moreover, he proves that the so-called shortness-exponent of the class \(\Gamma\) of all 5-regular multitriangular graphs is less than one. As a consequence, for some \(\sigma< 1\), there exist arbitrarily large members \(G\) of \(\Gamma\) such that \({\log c(G)\over \log|V(G)|}\leq \sigma\), where \(c(G)\) denotes the length of a longest cycle in \(G\).
reviewed by: Andreas Huck
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 896015
zbMATH Keywords: polyhedral graph
zbMATH Keywords: multitriangular graph
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: shortness-exponent
zbMATH Keywords: longest cycle
author: Hansjoachim Walther
MaRDI profile type: Publication
cites work: Shortness exponents of families of graphs
cites work: 5-regular 3-polytopal graphs with edges of only two types and shortness exponents less than one
cites work: Regular planar graphs with faces of only two types and shortness parameters
cites work: Hamiltonicity in multitriangular graphs
cites work: On Hamiltonian Circuits
full work available at URL: 0012-365x(95)00203-9
OpenAlex ID: W2078799062
description: scientific article; zbMATH DE number 896015