Conjecture on regular nut graphs from circulant and Cartesian graph constructions

Let D(n,t)\mathcal{D}(n,t) denote the graph used in the construction, let F3F_3 and F5F_5 be the graphs shown in the paper, and let \operatorname{\Box} denote the Cartesian product of graphs. A nut graph is a graph whose adjacency matrix has nullity one and whose corresponding nullvector has no zero entries. The constructions below are considered for integers t1t\geq 1. Regular nut graph construction conjecture. The following statements hold:

  1. D(4t+6,t)F5\mathcal{D}(4t+6,t)\operatorname{\Box}F_5 is a nut graph of degree 4t+54t+5 for every t1t\geq 1.
  2. D(4t+6,t)F3\mathcal{D}(4t+6,t)\operatorname{\Box}F_3 is a nut graph of degree 4t+34t+3 for t1t\geq 1 such that t≢0(mod3)t\not\equiv 0\pmod{3}.
  3. D(4t+10,t)F3\mathcal{D}(4t+10,t)\operatorname{\Box}F_3 is a nut graph of degree 4t+34t+3 for t1t\geq 1 such that t0(mod3)t\equiv 0\pmod{3}.

These constructions would provide infinite families of regular nut graphs in the specified degrees. The claim is presented as a conjecture in the source, and no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Nino Bašić, Ivan Damnjanović and Patrick W. Fowler, “On the degrees of regular nut graphs and Cayley nut graphs”, arXiv:2410.14063 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.