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/

[1] G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. Mélot, House of graphs: A database of interesting graphs, Discrete Appl. Math. 161 (2013) 311–314. doi:10.1016/j.dam.2012.07.018

[2] G. Brinkmann, J. Goedgebeur and B.D. McKay, Generation of cubic graphs, Discrete Math. Theor. Comput. Sci. 13 (2011) 69–80.

[3] K. Coolsaet, P.W. Fowler and J. Goedgebeur, homepage of Nutgen. http://caagt.ugent.be/nutgen/

[4] K. Coolsaet, P.W. Fowler and J. Goedgebeur, Generation and properties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018) 423–444.

[5] P.W. Fowler, B.T. Pickup, T.Z. Todorova, M. Borg and I. Sciriha, Omni-conducting and omni-insulating molecules, J. Chem. Phys. 140 (2014) 054115. doi:10.1063/1.4863559

[6] J.B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler construction, (2019). arXiv preprint arXiv:1904.02229

[7] D. Holt and G.F. Royle, A census of small transitive groups and vertex-transitive graphs, J. Symbolic Comput. (2019), in press. doi:10.1016/j.jsc.2019.06.006

[8] B.D. McKay and G.F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. 30 (1990) 161–176.

[9] M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999) 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2〈137::AID-JGT7〉3.0.CO;2-G

[10] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1998) 193–211. doi:10.1016/S0012-365X(97)00036-8

[11] I. Sciriha, On the rank of graphs, in: Combinatorics, Graph Theory and Algorithms, Vol. II, Y. Alavi, D.R. Lick and A. Schwenk (Ed(s)), (Springer, Michigan, 1999) 769–778.

[12] I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007) 451–462. doi:10.13001/1081-3810.1215

[13] I. Sciriha, Coalesced and embedded nut graphs in singular graphs, Ars Math. Contemp. 1 (2008) 20–31. doi:10.26493/1855-3974.20.7cc

[14] I. Sciriha and I. Gutman, Nut graphs: maximally extending cores, Util. Math. 54 (1998) 257–272.