Shortness exponent
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 is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as{{citation
| last1 = Grünbaum | first1 = Branko | author1-link = Branko Grünbaum
| last2 = Walther | first2 = Hansjoachim
| doi = 10.1016/0097-3165(73)90012-5
| journal = Journal of Combinatorial Theory
| mr = 0314691
| pages = 364–385
| series = Series A
| title = Shortness exponents of families of graphs
| volume = 14
| year = 1973| hdl = 10338.dmlcz/101257
| hdl-access = free
}}.
:
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 ,{{citation
| last1 = Moon | first1 = J. W.
| last2 = Moser | first2 = L. | author2-link = Leo Moser
| journal = Pacific Journal of Mathematics
| mr = 0154276
| pages = 629–631
| title = Simple paths on polyhedra
| volume = 13
| year = 1963 | doi=10.2140/pjm.1963.13.629| doi-access = free
}}. while it has also been proven that every polyhedral graph contains a cycle of length .{{citation
| last1 = Chen | first1 = Guantao
| last2 = Yu | first2 = Xingxing
| doi = 10.1006/jctb.2002.2113
| issue = 1
| journal = Journal of Combinatorial Theory
| mr = 1930124
| pages = 80–99
| series = Series B
| title = Long cycles in 3-connected graphs
| volume = 86
| year = 2002| doi-access = free
}}. 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 ) with shortness exponent 0. There are many additional known results on shortness exponents of restricted subclasses of planar and polyhedral graphs.
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.{{citation
| last1 = Bondy | first1 = J. A. | author1-link = John Adrian Bondy
| last2 = Simonovits | first2 = M. | author2-link = Miklós Simonovits
| doi = 10.4153/CJM-1980-076-2
| issue = 4
| journal = Canadian Journal of Mathematics
| mr = 590661
| pages = 987–992
| title = Longest cycles in 3-connected 3-regular graphs
| volume = 32
| year = 1980| doi-access = free
}}.{{citation
| last = Jackson | first = Bill
| doi = 10.1016/0095-8956(86)90024-9
| issue = 1
| journal = Journal of Combinatorial Theory
| mr = 854600
| pages = 17–26
| series = Series B
| title = Longest cycles in 3-connected cubic graphs
| volume = 41
| year = 1986| doi-access =
}}.
References
{{reflist}}