Existence of Regular Nut Graphs for Degree at Most 11

Discussiones Mathematicae Graph Theory

Goedgebeur Jan¹  Fowler Patrick W.²  Pisanski Tomaž³  Sciriha Irene⁴  Gauci John Baptist⁴ 

[1] Department of Applied Mathematics, Computer Science ---amp--- Statistics, Ghent University, Ghent, Belgium, Computer Science Department, University of Mons, Mons, Belgium;Department of Chemistry, University of Sheffield, Sheffield, United Kingdom;Department of Information Sciences and TechnologiesUniversity of Primorska, Koper, Slovenia, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia;Department of Mathematics, University of Malta, Msida, Malta;

关键词: nut graph;    core graph;    regular graph;    nullity;    05c30;    05c50;    05c75;    05c90;    68r10;   

DOI  :  10.7151/dmgt.2283

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown