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 $e$ is the shortness exponent of a graph family $\{\backslash mathcal\; 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 $\{\backslash mathcal\; F\}$ into a sequence $G\_0,\; G\_1,\; \backslash dots$, with $h(G)$ defined to be the length of the longest cycle in graph $G$, 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

}}.

:$\backslash liminf\_\{i\backslash to\backslash infty\}\; \backslash frac\{\backslash log\; h(G\_i)\}\{\backslash 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 $\backslash log\_3\; 2\backslash approx\; 0.631$. A construction based on kleetopes shows that some polyhedral graphs have longest cycle length $O(n^\{\backslash log\_3\; 2\})$,{{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 $\backslash Omega(n^\{\backslash log\_3\; 2\})$.{{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 $K\_\{2,n\}$) 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 =

}}.