Paper Info
Title
An upper bound on the shortness exponent of inscribable polytopes
Abstract
We show that there exist non-Hamiltonian, maximal planar, inscribable graphs. A graph is inscribable if it can be realized as the edges of the convex hull of a set of points lying on a sphere. The class of inscribable graphs is the same as the class of graphs that can be realized as a Delaunay triangulation augmented by the edges of the farthest-point Voronoï dual. We also establish an upper bound of log 9 8 = 0.94639 … for the shortness exponent of inscribable graphs. The shortness exponent is a measure of the extent to which a class of graphs fails to be Hamiltonian. It is defined to be the smallest α for which there is a sequence G n of graphs in the class with lim n → ∞ | G n | = ∞ and a constant c such that for all n , h(G n )⩽c·|G n | α where h ( G ) is the length of a longest cycle in G and | G | is the number of nodes of G .
Year
DOI
Venue
1989
10.1016/0095-8956(89)90008-7
J. Comb. Theory, Ser. B
Keywords
Field
DocType
inscribable polytopes,shortness exponent,upper bound
Graph theory,Discrete mathematics,Combinatorics,Exponent,Upper and lower bounds,Convex hull,Polytope,Voronoi diagram,Planar graph,Mathematics,Delaunay triangulation
Journal
Volume
Issue
ISSN
46
1
Journal of Combinatorial Theory, Series B
Citations 
PageRank 
References 
2
0.62
6
Authors
1
Name
Order
Citations
PageRank
Michael B. Dillencourt149857.58