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 {\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 {\mathcal F} into a sequence G_0, G_1, \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

}}.

:\liminf_{i\to\infty} \frac{\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\approx 0.631. A construction based on kleetopes shows that some polyhedral graphs have longest cycle length O(n^{\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 \Omega(n^{\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 =

}}.

References