HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the shortness exponent is a numerical parameter of a family of graphs that measures how far from
Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified 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 n^e but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in 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. :\liminf_ \frac. 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^),. while it has also been proven that every polyhedral graph contains a cycle of length \Omega(n^). 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_) 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

{{reflist Hamiltonian paths and cycles