On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs

Bašić, Nino ; Fowler, Patrick W. ; Pisanski, Tomaž ; Sciriha, Irene

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1351-1382.

Résumé

A signed graph has edge weights drawn from the set +1, −1, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph K_n for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.

Détail

Mots-clés : signed graph, nut graph, singular graph, graph spectrum, Fowler construction, sign-balanced graph, sign-unbalanced graph, cocktail-party graph

Bibliographie

[1] S. Akbari, S.M. Cioabă, S. Goudarzi, A. Niaparast and A. Tajdini, On a question of Haemers regarding vectors in the nullspace of Seidel matrices, Linear Algebra Appl. 615 (2021) 194–206. https://doi.org/10.1016/j.laa.2021.01.003

[2] I. Balla, F. Dräxler, P. Keevash and B. Sudakov, Equiangular lines and spherical codes in Euclidean space, Invent. Math. 211 (2018) 179–212. https://doi.org/10.1007/s00222-017-0746-0

[3] N. Bašić, P.W. Fowler, T. Pisanski and I. Sciriha, Signed nut graphs (2021). https://github.com/UP-LaTeR/signed-nut-graphs

[4] N. Bašić, M. Knor and R.Škrekovski, On 12 -regular nut graphs, Art Discrete Appl. Math. (2021), in-press. https://doi.org/10.26493/2590-9770.1403.1b1

[5] F. Belardo, S.M. Cioabă, J. Koolen and J. Wang, Open problems in the spectral theory of signed graphs, Art Discrete Appl. Math. 1 (2018) #P2.10. https://doi.org/10.26493/2590-9770.1286.d7b

[6] N. Biggs, Algebraic Graph Theory, 2nd Edition (Cambridge University Press, Cambridge, 1993). https://doi.org/10.1017/CBO9780511608704

[7] 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. https://doi.org/10.1016/j.dam.2012.07.018

[8] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012). https://doi.org/10.1007/978-1-4614-1939-6

[9] F.R.K. Chung, Spectral Graph Theory (American Mathematical Society, Providence, RI, 1997). https://doi.org/10.1090/cbms/092

[10] K. Coolsaet, P.W. Fowler and J. Goedgebeur, Nut graphs (2018). http://caagt.ugent.be/nutgen/

[11] K. Coolsaet, P.W. Fowler and J. Goedgebeur, Generation and properties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018) 423–444.

[12] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Johann Ambrosius Barth, Heidelberg, 1995).

[13] D.M. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997). https://doi.org/10.1017/cbo9781139086547

[14] D.M. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010). https://doi.org/10.1017/CBO9780511801518

[15] I. Damnjanović and D. Stevanović, On circulant nut graphs, Linear Algebra Appl. 633 (2022) 127–151. https://doi.org/10.1016/j.laa.2021.10.006

[16] F. Ema, M. Tanabe, S. Saito, T. Yoneda, K. Sugisaki, T. Tachikawa, S. Akimoto, S. Yamauchi, K. Sato, A. Osuka, T. Takui and Y. Kobori, Charge-transfer character drives Möbius antiaromaticity in the excited triplet state of twisted [28] hexaphyrin, J. Phys. Chem. Lett. 9 (2018) 2685–2690. https://doi.org/10.1021/acs.jpclett.8b00740

[17] P.W. Fowler, Hückel spectra of Möbius π systems, Phys. Chem. Chem. Phys. 4 (2002) 2878–2883. https://doi.org/10.1039/b201850k

[18] P.W. Fowler, J.B. Gauci, J. Goedgebeur, T. Pisanski and I. Sciriha, Existence of regular nut graphs for degree at most 11, Discuss. Math. Graph Theory 40 (2020) 533–557. https://doi.org/10.7151/dmgt.2283

[19] 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. https://doi.org/10.1063/1.4863559

[20] P.W. Fowler, T. Pisanski and N. Bašić, Charting the space of chemical nut graphs, MATCH Commun. Math. Comput. Chem. 86 (2021) 519–538.

[21] J.B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler construction, Appl. Anal. Discrete Math. (2021), in-press. https://doi.org/10.2298/aadm190517028g

[22] E. Ghorbani, W.H. Haemers, H.R. Maimani and L.P. Majd, On sign-symmetric signed graphs, Ars Math. Contemp. 19 (2020) 83–93. https://doi.org/10.26493/1855-3974.2161.f55

[23] G. Greaves, J.H. Koolen, A. Munemasa and F. Szöllősi, Equiangular lines in Euclidean spaces, J. Combin. Theory Ser. A 138 (2016) 208–235. https://doi.org/10.1016/j.jcta.2015.09.008

[24] W.H. Haemers, Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68 (2012) 653–659.

[25] E. Heilbronner, Hückel molecular orbitals of Möbius-type conformations of annulenes, Tetrahedron Lett. 5 (1964) 1923–1928. https://doi.org/10.1016/s0040-4039(01)89474-0

[26] R. Herges, Topology in chemistry: Designing Möbius molecules, Chem. Rev. 106 (2006) 4820–4842. https://doi.org/10.1021/cr0505425

[27] J.S. Maybee, D.D. Olesky and P. van den Driessche, Partly zero eigenvectors, Linear Multilinear Algebra 28 (1990) 83–92. https://doi.org/10.1080/03081089008818033

[28] J.J. McDonald, Partly zero eigenvectors and matrices that satisfy Au = b, Linear Multilinear Algebra 33 (1992) 163–170. https://doi.org/10.1080/03081089308818190

[29] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112. https://doi.org/10.1016/j.jsc.2013.09.003

[30] H.S. Rzepa, Möbius aromaticity and delocalization, Chem. Rev. 105 (2005) 3697–3715. https://doi.org/10.1021/cr030092l

[31] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1998) 193–211. https://doi.org/10.1016/s0012-365x(97)00036-8

[32] I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007) 451–462. https://doi.org/10.13001/1081-3810.1215

[33] I. Sciriha, Coalesced and embedded nut graphs in singular graphs, Ars Math. Contemp. 1 (2008) 20–31. https://doi.org/10.26493/1855-3974.20.7cc

[34] I. Sciriha, Maximal core size in singular graphs, Ars Math. Contemp. 2 (2009) 217–229. https://doi.org/10.26493/1855-3974.115.891

[35] I. Sciriha and L. Collins, Two-graphs and NSSDs: An algebraic approach, Discrete Appl. Math. 266 (2019) 92–102. https://doi.org/10.1016/j.dam.2018.05.003

[36] I. Sciriha and P.W. Fowler, Nonbonding orbitals in fullerenes: Nuts and cores in singular polyhedral graphs, J. Chem. Inf. Model. 47 (2007) 1763–1775. https://doi.org/10.1021/ci700097j

[37] I. Sciriha and I. Gutman, Nut graphs: Maximally extending cores, Util. Math. 54 (1998) 257–272.

[38] Z. Stanić, Perturbations in a signed graph and its index, Discuss. Math. Graph Theory 38 (2018) 841–852. https://doi.org/10.7151/dmgt.2035

[39] A. Streitwieser, Molecular Orbital Theory for Organic Chemists (Wiley, New York, 1961).

[40] N. Trinajstić, Chemical Graph Theory, 2nd Edition (CRC Press, Boca Raton, FL, 1992). https://doi.org/10.1201/9781315139111

[41] T. Yoneda, Y.M. Sung, J.M. Lim, D. Kim and A. Osuka, Pd^II complexes of [44]- and [46] decaphyrins: The largest Hückel aromatic and antiaromatic, and Möbius aromatic macrocycles, Angew. Chem. Int. Ed. 53 (2014) 13169–13173. https://doi.org/10.1002/anie.201408506

[42] Z.S. Yoon, A. Osuka and D. Kim, Möbius aromaticity and antiaromaticity in expanded porphyrins, Nature Chemistry 1 (2009) 113–122. https://doi.org/10.1038/nchem.172

[43] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47–74. https://doi.org/10.1016/0166-218x(82)90033-6

[44] T. Zaslavsky, Glossary of signed and gain graphs and allied areas, Electron. J. Combin., Dynamic Surveys (1998) #DS9. https://doi.org/10.37236/31

[45] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin., Dynamic Surveys (1998) #DS8. https://doi.org/10.37236/29