Nino Bašić: Nut graphs are not edge transitive

Abstract. A nut graph has a single non-trivial kernel eigenvector and that vector contains no zero entries. If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they are all connected, non-bipartite, and have no leaves. A nut graph may be vertex transitive; there are known examples of circulant nut graphs, Cayley nut graphs, and also non-Cayley vertex-transitive nut graphs. We will show that no nut graph can be edge transitive. Furthermore, a nut graph always has strictly more edge orbits than vertex orbits. We also construct several families of nut graphs with a low number of vertex orbits and edge orbits as regular coverings over certain voltage graphs (using non-cyclic groups).

This is joint work with Patrick W. Fowler and Tomaž Pisanski.