Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Harris graph
open-in-new
<h2 id="history">History</h2> <p>After Harris Spungen made his <a href="/facts/Conjecture/oPWUb7SF">conjecture</a> in 2013,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> Doug Shaw shortly discovered a <a href="/facts/Counterexample/dnThYpHW">counterexample</a>, 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.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p><p>In 2023, Akshay Anand implemented a Harris graph checker in <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> That same year, 241,375 Harris graphs were found of <a href="/facts/Order_of_a_graph/kw3eIBUe">order</a> 12 or less, and the Hirotaka graph was proven to be unique by code written by Shubhra Mishra and Marco Troper.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> The number of Harris graphs with n vertices was also made into an <a href="/facts/OEIS/yow6cVsU">OEIS</a> sequence.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p> <h2 id="construction">Construction</h2> <h3>Flowering a Harris graph</h3> <p>A k-barnacle is a <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a> of length k between two <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">nodes</a> where every node on the path has <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 2. Flowering is the process of adding a 2-barnacle between two nodes on the shortest path between two odd-degree nodes. </p><p>Flowering a <a href="/facts/Graph_toughness/92anGVk5">tough</a>, non-<a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian graph</a> that has an even number of nodes with odd degrees produces a Harris graph.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> 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 <a href="/facts/Eulerian_path/4l2G67c7">Eulerian</a> one as well. </p> <h3>Grafting two Harris graphs into one</h3> <p>A 5-<a href="/facts/Wheel_graph/rrQQSxNw">wheel</a> is added between one <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edge</a> in one Harris graph and another edge in another Harris graph, and two nodes from each 5-wheel are <a href="/facts/Connected_graph/FSNjsYhz">connected</a> 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.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h3>Replacing edges with barnacles</h3> <p>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 <a href="/facts/Graph_toughness/92anGVk5">toughness</a> remains the same, adding a barnacle anywhere keeps the graph Eulerian, tough, and non-Hamiltonian.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h2 id="types">Types</h2> <p>The Hirotaka graph, with 7 and <a href="/facts/Size_(graph_theory)/kw3eIBUe">size</a> 12, is the Harris graph with the smallest order.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> The first appearance of this graph was in a paper as an example of a non-Hamiltonian, tough graph.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> Douglas Shaw proved it to be minimal by showing all Eulerian graphs of order 6 or lower were not Hamiltonian and tough. <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a> code written by Shubhra Mishra and Marco Troper proved it unique.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p><p>The first Harris graph discovered was the Shaw graph, which has order 9 and size 14.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a><a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a><a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> This graph served as the counterexample to Harris Spungen's 2013 conjecture. </p><p>The minimal barnacle-free Harris graph, or the Lopez graph, has order 13 and size 33. It was constructed to address a <a href="/facts/Conjecture/oPWUb7SF">conjecture</a> that barnacle-free Harris graphs do not exist.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> </p> <h2 id="applications">Applications</h2> <p>Harris graphs are particularly valuable in teaching graph theory because they possess easily understandable properties and methods for finding and verifying them.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a><a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a> They offer an ideal balance between challenge and accessibility, making them an engaging problem for students at various levels.<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> </p><p>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.<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>"A366315 - OEIS". oeis.org. Retrieved 23 January 2025. <a href="https://oeis.org/A366315" target="_blank">https://oeis.org/A366315</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382" target="_blank">https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Anand, Akshay (12 July 2023). "Harris Graph Checker". Retrieved 7 July 2024. <a href="https://replit.com/@AkshayAnand4/HarrisGraphChecker" target="_blank">https://replit.com/@AkshayAnand4/HarrisGraphChecker</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>"A366315 - OEIS". oeis.org. Retrieved 23 January 2025. <a href="https://oeis.org/A366315" target="_blank">https://oeis.org/A366315</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Chvátal, V. (1 July 1973). "Tough graphs and hamiltonian circuits". Discrete Mathematics. 5 (3): 215–228. doi:10.1016/0012-365X(73)90138-6. ISSN 0012-365X. <a href="https://www.sciencedirect.com/science/article/pii/0012365X73901386" target="_blank">https://www.sciencedirect.com/science/article/pii/0012365X73901386</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>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. <a href="https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382" target="_blank">https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024. <a href="https://sites.google.com/view/harris-graphs/" target="_blank">https://sites.google.com/view/harris-graphs/</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>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. <a href="https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382" target="_blank">https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>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. <a href="https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382" target="_blank">https://www.tandfonline.com/doi/full/10.1080/07468342.2018.1507382</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> </ol>