Playing Checkers on a Donut: Visualizing the Only Vertex-Transitive Bipartite Quartic Integral Graph on 32 Vertices

摘要

The visualization of research outcomes can make complex content more readily accessible as well as inspire new ways of thinking about a problem. As a case in point, we present a recent result in spectral graph theory together with an intuitive visualization through which it can easily be grasped. An integral graph is a graph with only integers as eigenvalues, where the eigenvalues are calculated from the matrix representation of the graph. The spectrum of a graph is the set of distinct eigenvalues with their multiplicities. A list of candidates for the spectrum of a quartic integral graph that is both bipartite and vertex-transitive was previously determined and the question still remained: which graphs have a spectrum from this list? We are able to take the candidates from this list for graphs with 32 vertices, the smallest unknown case, and show that only one spectrum is realizable and that the graph that exists with this spectrum is unique. Despite substantial technical details required to derive the proof, we are also able to give a simple way of visualizing the unique graph that illustrates this result.