Bipartite edge frustration of nut graphs: proofs and constructions

Source abstract

The bipartite edge frustration of a graph $G$, $\varphi(G)$, is the minimum number of edges that must be removed from $G$ to obtain a graph that is bipartite. Core graphs are singular graphs on $2$ or more vertices, for which the kernel of the adjacency matrix contains a full eigenvector. A nut graph is a core graph of nullity one. Nut graphs $G$ are non-bipartite. It is proved here that $\varphi(G) \geq 2$ if $G$ is a nut graph, i.e. every nut graph requires deletion of at least two edges to produce a bipartite graph. In addition, we give a constructive proof that for every integer $k \geq 2$ there exist infinitely many chemical nut graphs $G$ with $\varphi(G) = k$. Furthermore, for $3 \leq d \leq 8$, the values $k$, for which a $d$-regular nut graph $G$ with $\varphi(G) = k$ exists, are characterised. It is shown here that for every integer $k \geq 2$ there exist infinitely many cubic polyhedral nut graphs $G$ with $\varphi(G) = k$. Two ways of producing larger nut graphs from smaller are described: the cut and frustration constructions. One straightforward consequence is that total double subdivision of a nut graph (i.e. simultaneous insertion of two degree-$2$ vertices into every edge) yields a nut graph.