Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/65149
Title: | Existence of regular nut graphs for degree at most 11 |
Authors: | Fowler, Patrick W. Gauci, John Baptist Goedgebeur, Jan Pisanski, Tomaź Sciriha, Irene |
Keywords: | Graph theory Mathematics Graph algorithms Nullity |
Issue Date: | 2020 |
Publisher: | Technical University Zielona Gora. Institute of Mathematics |
Citation: | Fowler, P. W., Gauci, J. B., Goedgebeur, J., Pisanski, T., & Sciriha, I. (2020). Existence of regular nut graphs for degree at most 11. Discussiones Mathematicae Graph Theory, 40(2), 533-557. |
Abstract: | 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. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/65149 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
DMGT-2283.pdf | 165.98 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.