A lower bound for the shortness coefficient of a class of graphs
type: Item
instance of: scholarly article
title: A lower bound for the shortness coefficient of a class of graphs
zbMATH Open document ID: 0803.05019
DOI: 10.1016/0166-218X(94)90098-1
author: Jochen Harant
author: Hansjoachim Walther
published in: Discrete Applied Mathematics
publication date: 1995-01-02T00:00:00Z
review text: Let \(X\) be a class of graphs. The shortness coefficient \(\rho(X)\) of class \(X\) is defined as \[ \rho(X)= \liminf_{G\in X} {c(G)\over n(G)}, \] where \(c(G)\) and \(n(G)\) denote the length of a longest circuit and the number of vertices of \(G\), respectively. For a positive integer \(q\), let \(S(5,q)\) be the class of all 3-regular planar 3-connected graphs in which each face is a 5-gon or a \(q\)-gon and two \(q\)-gons do not have a boundary edge in common. In this paper, the authors prove that for \(q\geq 13\), \[ \rho(S(5,q))\geq {2\over 3}+ {(q- 6)\over 9(q- 5)}, \] which improves upon a result in \textit{P. J. Owens} [Simple 3-polytopal graphs with edges of only two types and shortness coefficients, Discrete Math. 59, 107-114 (1986; Zbl 0586.05027)].
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 612434
zbMATH Keywords: shortness coefficient
zbMATH Keywords: longest circuit
zbMATH Keywords: \(q\)-gon
MaRDI profile type: Publication
cites work: Shortness exponents of families of graphs
cites work: On a class of Hamiltonian polytopes
cites work: On the simplicial 3-polytopes with only two types of edges
cites work: Simple 3-polytopal graphs with edges of only two types and shortness coefficients
cites work: On shortness coefficients of simple 3-polytopal graphs with only one type of faces besides triangles
full work available at URL: 0166-218x(94)90098-1
OpenAlex ID: W1998694031
description: scientific article; zbMATH DE number 612434