Geodesic
Existence of Regular Nut Graphs for Degree at Most 11
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 533-557

Voir la notice de l'article provenant de la source Library of Science

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 ≤ 4. Here we solve the problem for all remaining cases d ≤ 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 
@article{DMGT_2020_40_2_a10,
     author = {Fowler, Patrick W. and Gauci, John Baptist and Goedgebeur, Jan and Pisanski, Toma\v{z} and Sciriha, Irene},
     title = {Existence of {Regular} {Nut} {Graphs} for {Degree} at {Most} 11},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {533--557},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a10/}
}
TY  - JOUR
AU  - Fowler, Patrick W.
AU  - Gauci, John Baptist
AU  - Goedgebeur, Jan
AU  - Pisanski, Tomaž
AU  - Sciriha, Irene
TI  - Existence of Regular Nut Graphs for Degree at Most 11
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 533
EP  - 557
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a10/
LA  - en
ID  - DMGT_2020_40_2_a10
ER  - 
%0 Journal Article
%A Fowler, Patrick W.
%A Gauci, John Baptist
%A Goedgebeur, Jan
%A Pisanski, Tomaž
%A Sciriha, Irene
%T Existence of Regular Nut Graphs for Degree at Most 11
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 533-557
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a10/
%G en
%F DMGT_2020_40_2_a10
Fowler, Patrick W.; Gauci, John Baptist; Goedgebeur, Jan; Pisanski, Tomaž; Sciriha, Irene. Existence of Regular Nut Graphs for Degree at Most 11. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 533-557. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a10/