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 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.
Hypohamiltonian graphs were first studied by Sousselier (1963). Lindgren (1967) cites Gaudin, Herz & Rossi (1964) and Busacker & Saaty (1965) as additional early papers on the subject; another early work is by Herz, Duby & Vigué (1967).
Grötschel (1980) sums up much of the research in this area with the following sentence: “The articles dealing with those graphs ... usually exhibit new classes of hypohamiltonian or hypotraceable graphs showing that for certain orders n such graphs indeed exist or that they possess strange and unexpected properties.”
Hypohamiltonian graphs arise in integer programming solutions to the traveling salesman problem: certain kinds of hypohamiltonian graphs define facets of the traveling salesman polytope, a shape defined as the convex hull of the set of possible solutions to the traveling salesman problem, and these facets may be used in cutting-plane methods for solving the problem. [1] Grötschel (1980) observes that the computational complexity of determining whether a graph is hypohamiltonian, although unknown, is likely to be high, making it difficult to find facets of these types except for those defined by small hypohamiltonian graphs; fortunately, the smallest graphs lead to the strongest inequalities for this application. [2]
Concepts closely related to hypohamiltonicity have also been used by Park, Lim & Kim (2007) to measure the fault tolerance of network topologies for parallel computing.
Every hypohamiltonian graph must be 3-vertex-connected, as the removal of any two vertices leaves a Hamiltonian path, which is connected. There exist n-vertex hypohamiltonian graphs in which the maximum degree is n/2, and in which there are approximately n2/4 edges. [3]
Herz, Duby & Vigué (1967) conjectured that every hypohamiltonian graph has girth 5 or more, but this was disproved by Thomassen (1974b), who found examples with girth 3 and 4. For some time it was unknown whether a hypohamiltonian graph could be planar, but several examples are now known, [4] the smallest of which has 40 vertices. [5] Every planar hypohamiltonian graph has at least one vertex with only three incident edges. [6]
If a 3-regular graph is Hamiltonian, its edges can be colored with three colors: use alternating colors for the edges on the Hamiltonian cycle (which must have even length by the handshaking lemma) and a third color for all remaining edges. Therefore, all snarks, bridgeless cubic graphs that require four edge colors, must be non-Hamiltonian, and many known snarks are hypohamiltonian. Every hypohamiltonian snark is bicritical: removing any two vertices leaves a subgraph the edges of which can be colored with only three colors. [7] A three-coloring of this subgraph can be simply described: after removing one vertex, the remaining vertices contain a Hamiltonian cycle. After removing a second vertex, this cycle becomes a path, the edges of which may be colored by alternating between two colors. The remaining edges form a matching and may be colored with a third color.
The color classes of any 3-coloring of the edges of a 3-regular graph form three matchings such that each edge belongs to exactly one of the matchings. Hypohamiltonian snarks do not have a partition into matchings of this type, but Häggkvist (2007) conjectures that the edges of any hypohamiltonian snark may be used to form six matchings such that each edge belongs to exactly two of the matchings. This is a special case of the Berge–Fulkerson conjecture that any snark has six matchings with this property.
Hypohamiltonian graphs cannot be bipartite: in a bipartite graph, a vertex can only be deleted to form a Hamiltonian subgraph if it belongs to the larger of the graph's two color classes. However, every bipartite graph occurs as an induced subgraph of some hypohamiltonian graph. [8]
The smallest hypohamiltonian graph is the Petersen graph ( Herz, Duby & Vigué 1967 ). More generally, the generalized Petersen graph GP(n,2) is hypohamiltonian when n is 5 (mod 6); [9] the Petersen graph is the instance of this construction with n = 5.
Lindgren (1967) found another infinite class of hypohamiltonian graphs in which the number of vertices is 4 (mod 6). Lindgren's construction consists of a cycle of length 3 (mod 6) and a single central vertex; the central vertex is connected to every third vertex of the cycle by edges he calls spokes, and the vertices two positions away from each spoke endpoint are connected to each other. Again, the smallest instance of Lindgren's construction is the Petersen graph.
Additional infinite families are given by Bondy (1972), Doyen & van Diest (1975), and Gutt (1977).
Václav Chvátal proved in 1973 that for all sufficiently large n there exists a hypohamiltonian graph with n vertices. Taking into account subsequent discoveries, [10] “sufficiently large” is now known to mean that such graphs exist for all n ≥ 18. A complete list of hypohamiltonian graphs with at most 17 vertices is known: [11] they are the 10-vertex Petersen graph, a 13-vertex graph and a 15-vertex graph found by computer searches of Herz (1968), and four 16-vertex graphs. There exist at least thirteen 18-vertex hypohamiltonian graphs. By applying the flip-flop method of Chvátal (1973) to the Petersen graph and the flower snark, it is possible to show that the number of hypohamiltonian graphs, and more specifically the number of hypohamiltonian snarks, grows as an exponential function of the number of vertices. [12]
Graph theorists have also studied hypotraceable graphs, graphs that do not contain a Hamiltonian path but such that every subset of n − 1 vertices may be connected by a path. [13] Analogous definitions of hypohamiltonicity and hypotraceability for directed graphs have been considered by several authors. [14]
An equivalent definition of hypohamiltonian graphs is that their longest cycle has length n − 1 and that the intersection of all longest cycles is empty. Menke, Zamfirescu & Zamfirescu (1998) investigate graphs with the same property that the intersection of longest cycles is empty but in which the longest cycle length is shorter than n − 1. Herz (1968) defines the cyclability of a graph as the largest number k such that every k vertices belong to a cycle; the hypohamiltonian graphs are exactly the graphs that have cyclability n − 1. Similarly, Park, Lim & Kim (2007) define a graph to be ƒ-fault hamiltonian if the removal of at most ƒ vertices leaves a Hamiltonian subgraph. Schauerte & Zamfirescu (2006) study the graphs with cyclability n − 2.
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.
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. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete.
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.
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 the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.
In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.
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 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 the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.
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.
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 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 theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.
The Wiener–Araya graph is, in graph theory, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It is also planar.
The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.