{{Use dmy dates|date=July 2024}} {{Short description|Eulerian, non-hamiltonian, tough graph}} {{Distinguish|Harries graph}} [[File:Shaw Graph.png|thumb|The Shaw graph, the first known Harris graph, is of order 9 and size 14, discovered by Douglas Shaw.]]
In graph theory, a Harris graph is defined as an Eulerian, tough, non-Hamiltonian graph.<ref name=":0">{{Cite web|last=Mishra |first=Shubhra |title=Harris Graph Repository |url=https://sites.google.com/view/harris-graphs/ |access-date=2024-07-05 |website=sites.google.com}}</ref><ref name=":1">{{Cite arXiv |last1=Gandini |first1=Francesca |last2=Mishra |first2=Shubhra |last3=Shaw |first3=Douglas |date=December 18, 2023 |title=Families of Harris Graphs |class=math.CO |eprint=2312.10936}}</ref> Harris graphs were introduced in 2013 when, at the University of Michigan, Harris Spungen conjectured that any graph which is both tough and Eulerian is sufficiently Hamiltonian. However, Douglas Shaw disproved this conjecture, discovering a counterexample with order 9 and size 14.<ref name=":0" /> Currently, there are 241,375 known Harris graphs.<ref name=":1" /><ref name=":3">{{Cite oeis|A366315|Number of Harris graphs with n vertices}}</ref> The minimal Harris graph, the Hirotaka graph, has order 7 and size 12.<ref name=":0" /><ref name=":1" />
Harris graphs can be constructed by adding barnacles or grafting smaller Harris graphs, enabling larger graphs while preserving their properties. Notable types include the minimal Hirotaka graph, the barnacle-free Lopez graph, and the Shaw graph, each showcasing unique structural features in graph theory. Harris graphs are valuable for teaching graph theory due to their accessible methods for finding and verifying them. They offer a balanced challenge, fostering creativity, teamwork, and problem-solving as students collaborate to explore solutions.
==History== After Harris Spungen made his conjecture in 2013,<ref name=":2">{{Cite journal |last=Shaw |first=Douglas |date=November 16, 2018 |title=Harris Graphs—A Graph Theory Activity for Students and Their Instructors |url=https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382 |journal=The College Mathematics Journal |volume=49 |issue=5 |pages=323–326 |doi=10.1080/07468342.2018.1507382 |via=tandfonline|url-access=subscription }}</ref> 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.<ref name=":0" />
In 2023, and the Hirotaka graph was proven to be unique by code written by Shubhra Mishra and Marco Troper.<ref name=":1" /> The number of Harris graphs with n vertices was also made into an OEIS sequence.<ref name=":3" />
==Construction== ===Flowering a Harris graph=== A k-barnacle is a path of length k between two nodes where every node on the path has degree 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.<ref name=":1" /> Adding a 2-barnacle to a graph preserves its toughness while making it more difficult to be Hamiltonian. Furthermore, because a graph cannot have an odd number of vertices with odd degrees, the process of flowering can transform any non-Hamiltonian, tough graph into an Eulerian one as well.
===Grafting two Harris graphs into one=== 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. Since adding the connections and the 5-wheel does not cause the graph to be Hamiltonian, non-Eulerian, or not tough if it already met those conditions, the result will be one Harris graph.<ref name=":1" />
===Replacing edges with barnacles=== 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.<ref name=":1" />
==Types== [[File:Hirotaka Graph.png|thumb|The Hirotaka graph, discovered by Hirotaka Yoneda, consists of 7 nodes and 12 edges, and is the minimal and unique Harris graph.]]
The Hirotaka graph, with 7 and size 12, is the Harris graph with the smallest order.<ref name=":0" /><ref name=":1" /> The first appearance of this graph was as an example of a non-Hamiltonian, tough graph.<ref>{{Cite journal |last=Chvátal |first=V.|author-link=Václav Chvátal |date=1973-07-01 |title=Tough graphs and hamiltonian circuits |url=https://dx.doi.org/10.1016/0012-365X%2873%2990138-6 |journal=Discrete Mathematics |volume=5 |issue=3 |pages=215–228 |doi=10.1016/0012-365X(73)90138-6 |issn=0012-365X|url-access=subscription }}</ref> Douglas Shaw proved it to be minimal by showing all Eulerian graphs of order 6 or lower were not Hamiltonian and tough. Java code written by Shubhra Mishra and Marco Troper proved it unique.<ref name=":1" />
The first Harris graph discovered was the Shaw graph, which has order 9 and size 14.<ref name=":0" /><ref name=":1" /><ref name=":2" /> This graph served as the counterexample to Harris Spungen's 2013 conjecture.
The minimal barnacle-free Harris graph, or the Lopez graph, has order 13 and size 33. It was constructed to address a conjecture that barnacle-free Harris graphs do not exist.<ref name=":1" />
==Applications== Harris graphs are particularly valuable in teaching graph theory because they possess easily understandable properties and methods for finding and verifying them.<ref name=":0" /><ref name=":1" /> They offer an ideal balance between challenge and accessibility, making them an engaging problem for students at various levels.<ref name=":2" />
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.<ref name=":2" />
==References== {{Reflist}}
Category:Graph families