Draft:Harris graph
![]() | Review waiting, please be patient.
This may take 4 months or more, since drafts are reviewed in no specific order. There are 2,555 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
![](http://up.wiki.x.io/wikipedia/commons/thumb/b/b8/Shaw_Graph.png/220px-Shaw_Graph.png)
In graph theory, a Harris graph is defined as an Eulerian, non-Hamiltonian graph that satisfies the G / S condition.[1][2] Harris graphs were introduced in 2013 when, at the University of Michigan, Harris Spungen conjectured that an Eulerian graph meeting the G / S condition would also necessarily 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]
Making a Harris Graph
[edit]Flowering a Harris Graph
[edit]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 non-Hamiltonian graph that satisfies the G / S condition and has an even number of nodes with odd degrees produces a Harris graph.[2]
Grafting Two Harris Graphs into One
[edit]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 Edges with Barnacles
[edit]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, meeting the G / S condition, and non-Hamiltonian.[2]
Types of Harris Graphs
[edit]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]
![](http://up.wiki.x.io/wikipedia/commons/thumb/1/15/Hirotaka_Graph.png/220px-Hirotaka_Graph.png)
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]
History of Harris Graphs
[edit]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]
Applications of Harris Graphs
[edit]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]
References
[edit]- ^ a b c d e f g Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024.
- ^ a b c d e f g h i j k l Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO].
- ^ a b c d e Shaw, Douglas (16 November 2018). "Harris Graphs—A Graph Theory Activity for Students and Their Instructors". The College Mathematics Journal. 49 (5): 323–326. doi:10.1080/07468342.2018.1507382 – via tandfonline.
- ^ Anand, Akshay (12 July 2023). "Harris Graph Checker". Retrieved 7 July 2024.