This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these messages)
|
In graph theory, a Harris graph is defined as an Eulerian, tough, non-Hamiltonian graph. [1] [2] Harris graphs were introduced in 2013 when, at the University of Michigan, Harris Spungen conjectured that a tough, Eulerian graph would be sufficient to be Hamiltonian. [3] However, Douglas Shaw disproved this conjecture, discovering a counterexample with an order of 9 and a size of 14. [1] Currently, there are 241,375 known Harris graphs. [2] The minimal Harris graph, the Hirotaka graph, has an order of 7 and a size of 12. [1] [2]
After Harris Spungen made his conjecture in 2013, [3] Doug Shaw shortly discovered a counterexample, the Harris graph. Jayna Fishman and Elizabeth Petrie found two more Harris graphs in the same year. Over the next few years, three more Harris graphs were discovered, until Hirotaka Yoneda discovered what was thought to be the minimal Harris graph in 2018. [1] In 2023, Akshay Anand implemented a Harris graph checker in Java. [4] That same year, 241,375 Harris graphs were found of order 12 or less, and the Hirotaka graph was proven to be unique by code written by Shubhra Mishra and Marco Troper. [2]
A k-barnacle is a path between two nodes of length k where every node on the path has a degree of 2. Flowering is the process of adding a 2-barnacle between two nodes on the shortest path between two odd-degree nodes. Flowering a tough, non-Hamiltonian graph that has an even number of nodes with odd degrees produces a Harris graph. [2]
If a 5-wheel is added between one edge in one Harris graph and another edge in another Harris graph, and two nodes from each 5-wheel are connected to each other that were not connected to the original graph, then the result will be one Harris graph. [2]
Replacing an edge from an existing Harris graph with a 2-barnacle creates a Harris graph since all old degrees will be preserved, while the barnacle has a degree of 2 by definition, so the graph is still Eulerian. Since it is now even harder for the graph to be Hamiltonian, and since the graph's toughness remains the same, adding a barnacle anywhere keeps the graph Eulerian, tough, and non-Hamiltonian. [2]
The Hirotaka graph is the minimal Harris graph with order 7 and size 12. [1] [2] Douglas Shaw proved it to be minimal, and Java code written by Shubhra Mishra and Marco Troper proved it unique. [2]
The first Harris graph discovered was the Shaw graph, which has order 9 and size 14. [1] [2] [3]
The minimal barnacle-free Harris graph, or the Lopez graph, has order 13 and size 33. It was created in response to a conjecture that barnacle-free Harris graphs do not exist. [2]
Harris graphs are particularly valuable in teaching graph theory because they possess easily understandable properties and methods for finding and verifying them. [1] [2] They offer an ideal balance between challenge and accessibility, making them an engaging problem for students at various levels. [3]
Working with Harris graphs encourages students to experiment with different concepts and solutions, promoting creativity and mathematical thinking. This process keeps students engaged and collaborating with each other, as they often work together to verify potential solutions, enhancing teamwork and collective problem-solving skills. [3]
In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler, in 1736, laid the foundations of graph theory and prefigured the idea of topology.
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; see Hamiltonian path problem for details.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.
In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says:
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, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.
Václav (Vašek) Chvátal is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.
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 the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.
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.
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.
Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.
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.