Existence of regular nut graphs for degree at most 11

DOI10.7151/DMGT.2283MaRDI QIDQ2296003zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 11983 (Why is no real title available?)
• scientific article; zbMATH DE number 1248194 (Why is no real title available?)
• A census of small transitive groups and vertex-transitive graphs
• A characterization of singular graphs
• Coalesced and embedded nut graphs in singular graphs
• Fast generation of regular graphs and construction of cages
• Generation and properties of nut graphs
• Generation of cubic graphs
• House of Graphs: a database of interesting graphs
• On the construction of graphs of nullity one

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

Describes a project that uses

Uses Software

• snarkhunter
• GENREG
• House of Graphs

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)