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 is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as[1]
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 . A construction based on kleetopes shows that some polyhedral graphs have longest cycle length ,[2] while it has also been proven that every polyhedral graph contains a cycle of length .[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 ) 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]
^ abGrü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.
^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.
^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.
^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.
^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.
and 19 Related for: Shortness exponent information
In graph theory, the shortnessexponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family...
always written as a terminating decimal). The integer n is called the exponent and the real number m is called the significand or mantissa. The term "mantissa"...
In mathematics, the Lyapunov exponent or Lyapunov characteristic exponent of a dynamical system is a quantity that characterizes the rate of separation...
exponentiation is an operation involving two numbers: the base and the exponent or power. Exponentiation is written as bn, where b is the base and n is...
strongly, there exists a constant α < 1 {\displaystyle \alpha <1} (the shortnessexponent) and an infinite family of polyhedral graphs such that the length...
Critical exponents describe the behavior of physical quantities near continuous phase transitions. It is believed, though not proven, that they are universal...
The Hurst exponent is used as a measure of long-term memory of time series. It relates to the autocorrelations of the time series, and the rate at which...
lengths including a Hamiltonian cycle Seven Bridges of Königsberg Shortnessexponent, a numerical measure of how far from Hamiltonian the graphs in a family...
The Exponents, formerly The Dance Exponents, is a New Zealand rock group led by vocalist and songwriter Jordan Luck. Their major hits are "Victoria",...
The Angstrom exponent or Ångström exponent or absorption Ångström exponent is a parameter that describes how the optical thickness of an aerosol typically...
ISO 4217 is a standard published by the International Organization for Standardization (ISO) that defines alpha codes and numeric codes for the representation...
critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are...
In mathematics, characteristic exponent may refer to: Characteristic exponent of a field, a number equal to 1 if the field has characteristic 0, and equal...
The Exponent Telegram is a daily newspaper serving Clarksburg, West Virginia and the surrounding community. It has a daily print circulation of about 14...
tetrahedron, then its longest path has length O(nlog3 2); that is, the shortnessexponent of these graphs is log3 2, approximately 0.630930. The same technique...
The Purdue Exponent is an independent student newspaper that serves Purdue University in West Lafayette, Indiana. It is published on Mondays and Thursdays...
parts of the Floquet exponents are called Lyapunov exponents. The zero solution is asymptotically stable if all Lyapunov exponents are negative, Lyapunov...
The corpulence index uses an exponent of 3 rather than 2. The corpulence index yields valid results even for very short and very tall people, which is...
&{\mbox{if }}n{\mbox{ is even}}\end{cases}}} If the exponent n is zero then the answer is 1. If the exponent is negative then we can reuse the previous formula...
Global Information
