In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be.
is the shortness exponent of a graph family
-vertex graph in the family has a cycle of length near
but some graphs do not have longer cycles.
defined to be the length of the longest cycle in graph
, the shortness exponent is defined as[1] This number is always in the interval from 0 to 1; it is 1 for families of graphs that always contain a Hamiltonian or near-Hamiltonian cycle, and 0 for families of graphs in which the longest cycle length can be smaller than any constant power of the number of vertices.
The shortness exponent of the polyhedral graphs is
A construction based on kleetopes shows that some polyhedral graphs have longest cycle length
,[2] while it has also been proven that every polyhedral graph contains a cycle of length
There are many additional known results on shortness exponents of restricted subclasses of planar and polyhedral graphs.
[1] The 3-vertex-connected cubic graphs (without the restriction that they be planar) also have a shortness exponent that has been proven to lie strictly between 0 and 1.