Longest cycles in polyhedral graphs
type: Item
instance of: scholarly article
title: Longest cycles in polyhedral graphs
zbMATH Open document ID: 0784.05059
DOI: 10.1007/BF02764642
author: Hansjoachim Walther
published in: Israel Journal of Mathematics
publication date: 1994-03-17T00:00:00Z
review text: For a graph \(G\), let \(\nu(G)\) and \(c(G)\) be the number of vertices and the circumference of \(G\), respectively. If \(\Gamma\) is a family of graphs, the shortness exponent of \(\Gamma\), \(\sigma(\Gamma)\), is defined as \[ \sigma(\Gamma):=\liminf_{G\in \Gamma}{\log c(G)\over\log\nu(G)}. \] Several families of polyhedral graphs \(\Gamma\) are known such that \(\sigma(\Gamma)<1\) and \(\sigma(\Gamma^*)<1\),where \(\Gamma^*=\{G^*\mid G\) is in \(\Gamma\) and \(G^*\) is dual to \(G\}\). Constructed is a sequence \(\{G_ n\}\) of polyhedral graphs having only vertices of degree 3 and 8 and only triangles and octagons as faces such that \(\sigma(\{G_ n\})<1\) and \(\sigma(\{G^*_ n\})<1\). The construction starts with a certain non-Hamiltonian graph \(G_ 1\) on 14 vertices. It proceeds by a process of replacing each 3-valent vertex by a modified \(G_ 1\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 52B05
zbMATH DE Number: 446869
zbMATH Keywords: shortness exponent
zbMATH Keywords: polyhedral graphs
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: On shortness exponents of families of graphs
cites work: Shortness exponents of families of graphs
cites work: Longest Simple Paths in Polyhedral Graphs
cites work: Regular planar graphs with faces of only two types and shortness parameters
cites work: On shortness coefficients of simple 3-polytopal graphs with only one type of faces besides triangles
full work available at URL: https://doi.org/10.1007/bf02764642
OpenAlex ID: W1975980926
description: scientific article; zbMATH DE number 446869