Article in volume
Authors:
Title:
On singular signed graphs with nullspace spanned by a full vector: signed nut graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1351-1382
Received: 2021-01-27 , Revised: 2021-10-14 , Accepted: 2021-10-14 , Available online: 2021-10-25 , https://doi.org/10.7151/dmgt.2436
Abstract:
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 $(\rho,n)$
for which a $\rho$-regular nut graph (sign-balanced or sign-unbalanced) of order
$n$ exists with $\rho \le 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 $\rho$-regular nut graphs. Orders for which a regular nut
graph with $\rho = n-1$ exists are characterised; they are
sign-unbalanced with an underlying graph $K_n$ for which $n\equiv 1
\pmod 4$. Orders for which a regular sign-unbalanced nut graph with
$\rho = n - 2$ exists are also characterised; they have an underlying
cocktail-party graph CP$(n)$ with even order $n \geq 8$.
Keywords:
signed graph, nut graph, singular graph, graph spectrum, Fowler construction, sign-balanced graph, sign-unbalanced graph, cocktail-party graph
References:
- 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 - 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 - N. Bašić, P.W. Fowler, T. Pisanski and I. Sciriha, Signed nut graphs (2021).
https://github.com/UP-LaTeR/signed-nut-graphs - 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 - 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 - N. Biggs, Algebraic Graph Theory, 2nd Edition (Cambridge University Press, Cambridge, 1993).
https://doi.org/10.1017/CBO9780511608704 - 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 - A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012).
https://doi.org/10.1007/978-1-4614-1939-6 - F.R.K. Chung, Spectral Graph Theory (American Mathematical Society, Providence, RI, 1997).
https://doi.org/10.1090/cbms/092 - K. Coolsaet, P.W. Fowler and J. Goedgebeur, Nut graphs (2018).
http://caagt.ugent.be/nutgen/ - K. Coolsaet, P.W. Fowler and J. Goedgebeur, Generation and properties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018) 423–444.
- D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Johann Ambrosius Barth, Heidelberg, 1995).
- D.M. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997).
https://doi.org/10.1017/cbo9781139086547 - 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 - 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 - 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 - P.W. Fowler, Hückel spectra of Möbius $\pi$ systems, Phys. Chem. Chem. Phys. 4 (2002) 2878–2883.
https://doi.org/10.1039/b201850k - 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 - 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 - 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.
- 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 - 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 - 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 - W.H. Haemers, Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68 (2012) 653–659.
- 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 - R. Herges, Topology in chemistry: Designing Möbius molecules, Chem. Rev. 106 (2006) 4820–4842.
https://doi.org/10.1021/cr0505425 - 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 - 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 - 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 - H.S. Rzepa, Möbius aromaticity and delocalization, Chem. Rev. 105 (2005) 3697–3715.
https://doi.org/10.1021/cr030092l - 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 - I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007) 451–462.
https://doi.org/10.13001/1081-3810.1215 - 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 - I. Sciriha, Maximal core size in singular graphs, Ars Math. Contemp. 2 (2009) 217–229.
https://doi.org/10.26493/1855-3974.115.891 - 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 - 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 - I. Sciriha and I. Gutman, Nut graphs: Maximally extending cores, Util. Math. 54 (1998) 257–272.
- 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 - A. Streitwieser, Molecular Orbital Theory for Organic Chemists (Wiley, New York, 1961).
- N. Trinajstić, Chemical Graph Theory, 2nd Edition (CRC Press, Boca Raton, FL, 1992).
https://doi.org/10.1201/9781315139111 - T. Yoneda, Y.M. Sung, J.M. Lim, D. Kim and A. Osuka, Pd$^\textrm{ 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 - 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 - T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47–74.
https://doi.org/10.1016/0166-218x(82)90033-6 - T. Zaslavsky, Glossary of signed and gain graphs and allied areas, Electron. J. Combin., Dynamic Surveys (1998) #DS9.
https://doi.org/10.37236/31 - 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
Close