Raziskovalni matematični seminar - Arhiv

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.