Shortness exponent explained

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. Intuitively, if

e is the shortness exponent of a graph family { l F} , then every n -vertex graph in the family has a cycle of length near n ^{e} but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in { l F} into a sequence G _{0,} G _{1,} ... , with h(G) defined to be the length of the longest cycle in graph G , the shortness exponent is defined as^[1] \liminf _{i\toinfty} (log h(G _{i)})/(log |V(G _{i)|}) . 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

log _{3} 2 ≈ 0 . 631 . A construction based on kleetopes shows that some polyhedral graphs have longest cycle length O(n ^{log _{3} 2} ) ,^[2] while it has also been proven that every polyhedral graph contains a cycle of length \Omega(n ^{log _{3} 2} ) .^[3] The polyhedral graphs are the graphs that are simultaneously planar and 3-vertex-connected; the assumption of 3-vertex-connectivity is necessary for these results, as there exist sets of 2-vertex-connected planar graphs (such as the complete bipartite graphs K _{2,n} ) with shortness exponent 0. 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.^{[4] [5]}

Notes and References

1. .
2. .
3. .
4. .
5. .