Shortness exponent

Last updated August 16, 2023

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 ${\mathcal {F}}$ , 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 ${\mathcal {F}}$ 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^[1]

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

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

<span class="mw-page-title-main">Peripheral cycle</span> Graph cycle which does not separate remaining elements

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In geometry and polyhedral combinatorics, the Kleetope of a polyhedron or higher-dimensional convex polytope $P$ is another polyhedron or polytope $P K$ formed by replacing each facet of $P$ with a shallow pyramid. Kleetopes are named after Victor Klee.

In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if $is a 2-vertex-connected graph, then the square of is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.$

In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

References

1 2 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 .
↑ 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 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[gw-1] 1 2 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 .

[mm-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 .

[1]

[2]

[3]

[4]

[5]