Harris graph

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.[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]

  1. ^ a b c Mishra, Shubhra. "Harris Graph Repository". sites.google.com. Retrieved 5 July 2024.
  2. ^ a b c Gandini, Francesca; Mishra, Shubhra; Shaw, Douglas (18 December 2023). "Families of Harris Graphs". arXiv:2312.10936 [math.CO].
  3. ^ 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.