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 ℱ, then every n-vertex graph in the family has a cycle of length near ne but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in ℱ into a sequence G0,G1,…, with h(G) defined to be the length of the longest cycle in graph G, the shortness exponent is defined as[1]

lim infi->∞log⁡h(Gi)log⁡|V(Gi)|.

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 log32≈0.631. A construction based on kleetopes shows that some polyhedral graphs have longest cycle length O(nlog32),[2] while it has also been proven that every polyhedral graph contains a cycle of length Ω(nlog32).[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 K2,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]

## 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=260646"