DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

P.W. Fowler, J.B. Gauci, J. Goedgebeur, T. Pisanski, I. Sciriha

Title:

Existence of regular nut graphs for degree at most 11

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-08-30, Revised: 2019-11-06, Accepted: 2019-11-07, https://doi.org/10.7151/dmgt.2283

Abstract:

A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements. The problem of determining the orders $n$ for which $d$-regular nut graphs exist was recently posed by Gauci, Pisanski and Sciriha. These orders are known for $d \leq 4$. Here we solve the problem for all remaining cases $d\leq 11$ and determine the complete lists of all $d$-regular nut graphs of order $n$ for small values of $d$ and $n$. The existence or non-existence of small regular nut graphs is determined by a computer search. The main tool is a construction that produces, for any $d$-regular nut graph of order $n$, another $d$-regular nut graph of order $n + 2d$. If we are given a sufficient number of $d$-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all $d$-regular nut graphs of higher orders is established. For even $d$ the orders $n$ are indeed consecutive, while for odd $d$ the orders $n$ are consecutive even numbers. Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.

Keywords:

nut graph, core graph, regular graph, nullity

PDF
Close