Mathematical Research Seminar - Archive

A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an ℓ-circulant graph is a graph that admits a cyclic group of automorphisms having ℓ vertex orbits of equal size. It is not difficult to verify that there is no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of cubic 3-circulant nut graphs was recently obtained [Electron. J. Comb. 31(2) (2024), #2.31]. Here, we investigate the existence of cubic ℓ-circulant nut graphs for ℓ ≥ 4 and show that there is no cubic ℓ-circulant nut graph for ℓ ∈ {4, 5}, while there are infinitely many cubic ℓ-circulant nut graphs for each ℓ ∈ {6, 7} or ℓ ≥ 9. We also prove that there are infinitely many d-regular nut graphs for each d ≥ 3.

This is a joint work with Nino Bašić and Patrick W. Fowler.

A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry. Nut graphs have been established in the literature for quite some time; they were introduced in 1998 by Sciriha and Gutman. First, we present some well-known results. Nut graphs have seven or more vertices; they are all connected, non-bipartite, and leafless. Several constructions for nut graphs from smaller starting graphs are known (e.g., the Fowler construction); to these we add multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs). A class of particular interest is the class of chemical (i.e. subcubic) nut graphs; all $(v_3, v_2)$ pairs, for which a chemical nut graphs with $v_3$ degree-3 and $v_2$ degree-2 vertices exist, were characterised a few years ago.

In this talk, we will focus on certain symmetry properties of nut graphs. First, we show by construction that every finite group can be represented as the group of automorphisms of infinitely many (regular) nut graphs. Next, we show that a nut graph always has at least one more edge orbit than it has vertex orbits. In particular, edge-transitive nut graphs do not exist. We also give infinite families of vertex-transitive nut graphs with two orbits of edges.