Vertex-transitive nut graph order-degree existence problem
Abstract
A nut graph is a nontrivial simple graph whose adjacency matrix has a simple eigenvalue zero such that the corresponding eigenvector has no zero entries. It is known that the order $n$ and degree $d$ of a vertex-transitive nut graph satisfy $4 \mid d$, $d \ge 4$, $2 \mid n$ and $n \ge d + 4$; or $d \equiv 2 \pmod 4$, $d \ge 6$, $4 \mid n$ and $n \ge d + 6$. Here, we prove that for each such $n$ and $d$, there exists a $d$-regular Cayley nut graph of order $n$. As a direct consequence, we obtain all the pairs $(n, d)$ for which there is a $d$-regular vertex-transitive (resp. Cayley) nut graph of order $n$.
Fields of Study & Subjects
Graph theory and applications
Finite Group Theory Research
Advanced Graph Theory Research
Publication details
- Journal / source
- Discrete Mathematics & Theoretical Computer Science
- Volume
- vol. 28:2
- Issue
- Graph Theory
- Publication date
- 10 January 2026
- Language
- EN