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

[math]\displaystyle{ \liminf_{i\to\infty} \frac{\log h(G_i)}{\log |V(G_i)|}. }[/math]

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 [math]\displaystyle{ \log_3 2\approx 0.631 }[/math]. A construction based on kleetopes shows that some polyhedral graphs have longest cycle length [math]\displaystyle{ O(n^{\log_3 2}) }[/math],[2] while it has also been proven that every polyhedral graph contains a cycle of length [math]\displaystyle{ \Omega(n^{\log_3 2}) }[/math].[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 [math]\displaystyle{ K_{2,n} }[/math]) 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]

## References

1. ↑ 1.0 1.1 "Shortness exponents of families of graphs", Journal of Combinatorial Theory, Series A 14: 364–385, 1973, doi:10.1016/0097-3165(73)90012-5 .
2. ↑ Moon, J. W. (1963), "Simple paths on polyhedra", Pacific Journal of Mathematics 13: 629–631, doi:10.2140/pjm.1963.13.629 .
3. ↑ Chen, Guantao; Yu, Xingxing (2002), "Long cycles in 3-connected graphs", Journal of Combinatorial Theory, Series B 86 (1): 80–99, doi:10.1006/jctb.2002.2113 .
4. ↑ "Longest cycles in 3-connected 3-regular graphs", Canadian Journal of Mathematics 32 (4): 987–992, 1980, doi:10.4153/CJM-1980-076-2 .
5. ↑ Jackson, Bill (1986), "Longest cycles in 3-connected cubic graphs", Journal of Combinatorial Theory, Series B 41 (1): 17–26, doi:10.1016/0095-8956(86)90024-9 .

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Shortness exponent. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Shortness_exponent&oldid=3358279"