Existence of regular nut graphs for degree at most 11

DOI10.7151/DMGT.2283zbMATH Open1433.05153arXiv1908.11635OpenAlexW2996934332WikidataQ126431046 ScholiaQ126431046MaRDI QIDQ2296003FDOQ2296003

Authors: John Baptist Gauci, Jan Goedgebeur, Tomaž Pisanski, Irene Sciriha, Patrick W. Fowler 

Publication date: 17 February 2020

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: A nut graph is a singular graph with one-dimensional kernel and corresponding eigenverctor 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 $dleq4$. Here we solve the problem for all remaining cases $dleq11$ 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.

Full work available at URL: https://arxiv.org/abs/1908.11635

Recommendations

• On 12-regular nut graphs
• On circulant nut graphs
• Generation and properties of nut graphs
• scientific article; zbMATH DE number 1248194
• Coalesced and embedded nut graphs in singular graphs

zbMATH Keywords

regular graphnullitynut graphcore graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Cites Work

• House of Graphs: a database of interesting graphs
• Generation of cubic graphs
• Fast generation of regular graphs and construction of cages
• A characterization of singular graphs
• On the construction of graphs of nullity one
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coalesced and embedded nut graphs in singular graphs
• A census of small transitive groups and vertex-transitive graphs
• Generation and properties of nut graphs

Cited In (9)

• On 12-regular nut graphs
• Complete resolution of the circulant nut graph order-degree existence problem
• Classification of cubic tricirculant nut graphs
• Vertex and edge orbits in nut graphs
• On singular signed graphs with nullspace spanned by a full vector: signed nut graphs
• Existence of regular nut graphs and the fowler construction
• On circulant nut graphs
• Coalesced and embedded nut graphs in singular graphs
• Reconstruction from one labelled card and more

Uses Software

• House of Graphs
• GENREG
• snarkhunter

This page was built for publication: Existence of regular nut graphs for degree at most 11

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2296003)