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 ${\displaystyle e}$ is the shortness exponent of a graph family ${\displaystyle {ℱ}}$, 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 {ℱ}}$ 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^[1]

${\displaystyle \underset{i\to \mathrm{\infty }}{\mathrm{lim\; inf}}\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})}$,^[2] while it has also been proven that every polyhedral graph contains a cycle of length ${\displaystyle \mathrm{\Omega }(n^{{\log }_{3}2})}$.^[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 ${\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.^[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]

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Shortness exponent. Read more