×

zbMATH — the first resource for mathematics

Existence of regular nut graphs for degree at most 11. (English) Zbl 1433.05153
Summary: 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 B. Gauci et al. [“Existence of regular nut graphs and the Fowler construction”, Preprint, arXiv:1904.02229]. These orders are known for \(d \leq 4\). Here we solve the problem for all remaining cases \(d \leq 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.
MSC:
05C30 Enumeration in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[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 · Zbl 1292.05254
[2] G. Brinkmann, J. Goedgebeur and B.D. McKay, Generation of cubic graphs, Discrete Math. Theor. Comput. Sci. 13 (2011) 69-80. · Zbl 1283.05256
[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. · Zbl 0805.05037
[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 · Zbl 0918.05062
[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 · Zbl 0901.05069
[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 · Zbl 1142.05344
[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 · Zbl 1168.05330
[14] I. Sciriha and I. Gutman, Nut graphs: maximally extending cores, Util. Math. 54 (1998) 257-272. · Zbl 0919.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.