Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Vertex-transitive nu ...
Article

Vertex-transitive nut graph order-degree existence problem

Ivan Damnjanović (1) (2)
(1) University of Primorska
(2) University of Nis
Download article
Open on arXiv
Submitted on
July 4, 2025
Accepted on
December 28, 2025
Published on
January 10, 2026
Last modified on
January 10, 2026
Volume 28
vol. 28:2
Graph Theory
DOI
10.46298/dmtcs.15989
License
arXiv.org - Non-exclusive license to distribute
Indicators
553
Views
986
Downloads

Vertex-transitive nut graph order-degree existence problem

Ivan Damnjanović (1) (2)
(1) University of Primorska
(2) University of Nis
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$.
Keywords
  • Combinatorics
  • Number Theory
  • 05C50, 05C25, 11C08, 12D05
Mathematics Subject Classification 2020
  • 05C25 - Graphs and abstract algebra (groups, rings, fields, etc.)
  • 05C50 - Graphs and linear algebra (matrices, eigenvalues, etc.)
  • 11C08 - Polynomials in number theory
  • 12D05 - Polynomials in real and complex fields: factorization
  • 15A18 - Eigenvalues, singular values, and eigenvectors
Linked publications - datasets - software
  • Continues
    https://doi.org/10.26493/1855-3974.3009.6df
  • Continues
    https://doi.org/10.26493/2590-9770.1662.4e9
  • Is supplemented by
    https://github.com/Ivan-Damnjanovic/vt-nut-graphs
Preview
Loading PDF preview...