Misplaced Pages

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

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

References

1. ^ Grünbaum, Branko; Walther, Hansjoachim (1973), "Shortness exponents of families of graphs", Journal of Combinatorial Theory, Series A, 14: 364–385, doi:10.1016/0097-3165(73)90012-5, hdl:10338.dmlcz/101257, MR 0314691.
2. Moon, J. W.; Moser, L. (1963), "Simple paths on polyhedra", Pacific Journal of Mathematics, 13: 629–631, doi:10.2140/pjm.1963.13.629, MR 0154276.
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, MR 1930124.
4. Bondy, J. A.; Simonovits, M. (1980), "Longest cycles in 3-connected 3-regular graphs", Canadian Journal of Mathematics, 32 (4): 987–992, doi:10.4153/CJM-1980-076-2, MR 0590661.
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, MR 0854600.

• Hamiltonian paths and cycles