×

An arithmetic criterion for graphs being determined by their generalized \(A_\alpha \)-spectra. (English) Zbl 1466.05122

Summary: Let \(G\) be a graph on \(n\) vertices, its adjacency matrix and degree diagonal matrix are denoted by \(A(G)\) and \(D(G)\), respectively. V. Nikiforov [“Merging the A- and Q-spectral theories”, Appl. Anal. Discrete Math. 11, 81–107 (2017; doi:10.2298/AADM1701081N)] introduced the matrix \(A_\alpha(G) = \alpha D(G) +(1 - \alpha) A(G)\) for \(\alpha \in [0, 1]\). The \(A_\alpha \)-spectrum of a graph \(G\) consists of all the eigenvalues (including the multiplicities) of \(A_\alpha(G)\). A graph \(G\) is said to be determined by the generalized \(A_\alpha \)-spectrum (or, \(\mathrm{DGA}_\alpha \mathrm{S}\) for short) if whenever \(H\) is a graph such that \(H\) and \(G\) share the same \(A_\alpha \)-spectrum and so do their complements, then \(H\) is isomorphic to \(G\). In this paper, when \(\alpha\) is rational, we present a simple arithmetic condition for a graph being \(\mathrm{DGA}_\alpha \mathrm{S}\). More precisely, put \(A_{c_\alpha} : = c_\alpha A_\alpha(G)\), here \(c_\alpha\) is the smallest positive integer such that \(A_{c_\alpha}\) is an integral matrix. Let \(\tilde{W}_\alpha(G) = \left[ \mathfrak{1} , \frac{ A_{c_\alpha} \mathfrak{1}}{ c_\alpha} , \ldots , \frac{ A_{c_\alpha}^{n - 1} \mathbf{1}}{ c_\alpha} \right]\), where \(\mathfrak{1}\) denotes the all-ones column vector. We prove that if \(\frac{ \det \tilde{W}_\alpha ( G )}{ 2^{\lfloor \frac{ n}{ 2} \rfloor}}\) is an odd and square-free integer and the rank of \(\tilde{W}_\alpha(G)\) is full over \(\mathbb{F}_p\) for each odd prime divisor \(p\) of \(c_\alpha \), then \(G\) is \(\mathrm{DGA}_\alpha \mathrm{S}\) except for even \(n\) and odd \(c_\alpha\) (\(\geqslant 3\)). By our obtained results in this paper we may deduce the main results in [L. Qiu et al., Discrete Math. 342, No. 10, 2770–2782 (2019; Zbl 1417.05123)] and [W. Wang, J. Comb. Theory, Ser. B 122, 438–451 (2017; Zbl 1350.05098)].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15B36 Matrices of integers

Software:

Mathematica
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abiad, A.; Haemers, W. H., Cospectral graphs and regular orthogonal matrices of level 2, Electron. J. Comb., 19, 3, Article P13 pp. (2012) · Zbl 1253.05092
[2] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2012), Springer: Springer New York · Zbl 1231.05001
[3] Chen, Y. Y.; Li, D.; Meng, J. X., On the second largest \(A_\alpha \)-eigenvalues of graphs, Linear Algebra Appl., 580, 343-358 (2019) · Zbl 1420.05099
[4] Cohen, H., A Course in Computational Algebraic Number Theory, Graduate Texts in Math. (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0786.11071
[5] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[6] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156
[7] Desai, M.; Rao, V., A characterization of the smallest eigenvalue of a graph, J. Graph Theory, 18, 2, 181-194 (1994) · Zbl 0792.05096
[8] Fisher, M., On hearing the shape of a drum, J. Comb. Theory, 1, 105-125 (1966) · Zbl 0139.43302
[9] Günthard, Hs. H.; Primas, H., Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen, Helv. Chim. Acta, 39, 1645-1653 (1956)
[10] Huang, X.; Lin, H. Q.; Xue, J., The Nordhaus-Gaddum type inequalities of \(A_\alpha \)-matrix, Appl. Math. Comput., 365, Article 124716 pp. (2020) · Zbl 1433.05197
[11] Kac, M., Can one hear the shape of a drum?, Am. Math. Mon., 73, 1-23 (1966) · Zbl 0139.05603
[12] Li, D.; Chen, Y. Y.; Meng, J. X., The \(A_\alpha \)-spectral radius of trees and unicyclic graphs with given degree sequence, Appl. Math. Comput., 363, Article 124622 pp. (2019) · Zbl 1433.05201
[13] Li, S. C.; Sun, W. T., An arithmetic criterion for graphs being determined by their generalized \(A_\alpha \)-spectrum
[14] Li, S. C.; Wang, S. J., The \(A_\alpha \)-spectrum of graph product, Electron. J. Linear Algebra, 35, 473-481 (2019) · Zbl 1496.05098
[15] Li, S. C.; Wei, W., The multiplicity of an \(A_\alpha \)-eigenvalue: a unified approach for mixed graphs and complex unit gain graphs, Discrete Math., 343, 8, Article 111916 pp. (2020) · Zbl 1441.05142
[16] Lin, H. Q.; Huang, X.; Xue, J., A note on the \(A_\alpha \)-spectral radius of graphs, Linear Algebra Appl., 557, 430-437 (2018) · Zbl 1396.05073
[17] Liu, F. J.; Siemons, J.; Wang, W., New families of graphs determined by their generalized spectrum, Discrete Math., 342, 1108-1112 (2019) · Zbl 1405.05105
[18] Liu, F. J.; Wang, W.; Yu, T.; Lai, H.-J., Generalized cospectral graphs with and without Hamiltonian cycles, Linear Algebra Appl., 585, 199-208 (2020) · Zbl 1426.05104
[19] Mao, L. H.; Liu, F. J.; Wang, W., A new method for constructing graphs determined by their generalized spectrum, Linear Algebra Appl., 477, 112-127 (2015) · Zbl 1311.05117
[20] Nikiforov, V., Merging the A- and Q-spectral theories, Appl. Anal. Discrete Math., 11, 81-107 (2017) · Zbl 1499.05384
[21] Nikiforov, V.; Pastén, G.; Rojo, O.; Soto, R. L., On the \(A_\alpha \)-spectra of trees, Linear Algebra Appl., 520, 286-305 (2017) · Zbl 1357.05089
[22] Nikiforov, V.; Rojo, O., A note on the positive semidefiniteness of \(A_\alpha(G)\), Linear Algebra Appl., 519, 156-163 (2017) · Zbl 1357.05090
[23] Nikiforov, V.; Rojo, O., On the α-index of graphs with pendent paths, Linear Algebra Appl., 550, 87-104 (2018) · Zbl 1385.05051
[24] Qiu, L. H.; Ji, Y. Z.; Wang, W., A new arithmetic criterion for graphs being determined by their generalized Q-spectrum, Discrete Math., 342, 2770-2782 (2019) · Zbl 1417.05123
[25] Schrijver, A., The Theory of Linear and Integer Programming (1998), John Wiley & Sons · Zbl 0970.90052
[26] Wang, W., Generalized spectral characterization revisited, Electron. J. Comb., 20, 4, Article P4 pp. (2013) · Zbl 1298.05214
[27] Wang, W., A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Comb. Theory, Ser. B, 122, 438-451 (2017) · Zbl 1350.05098
[28] Wang, W.; Mao, L. H., A remark on the generalized spectral characterization of the disjoint union of graphs, Linear Algebra Appl., 518, 1-13 (2017) · Zbl 1354.05083
[29] Wang, W.; Qiu, L. H.; Hu, Y. L., Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p, Linear Algebra Appl., 563, 154-177 (2019) · Zbl 1405.05108
[30] Wang, J. F.; Wang, J.; Liu, X. G.; Belardo, F., Graphs whose \(A_\alpha \)-spectral radius does not exceed 2, Discuss. Math., Graph Theory, 40, 677-690 (2020) · Zbl 1433.05213
[31] Wang, S.; Wong, D.; Tian, F. L., Bounds for the largest and the smallest \(A_\alpha\) eigenvalues of a graph in terms of vertex degrees, Linear Algebra Appl., 590, 210-223 (2020) · Zbl 1437.05151
[32] Wang, W.; Xu, C. X., An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra, Linear Algebra Appl., 418, 62-74 (2006) · Zbl 1105.05050
[33] Wang, W.; Xu, C. X., A sufficient condition for a family of graphs being determined by their generalized spectra, Eur. J. Comb., 27, 826-840 (2006) · Zbl 1092.05050
[34] Wang, W.; Xu, C. X., Note: on the generalized spectral characterization of graphs having an isolated vertex, Linear Algebra Appl., 425, 210-215 (2007) · Zbl 1118.05065
[35] Wolfram Research, Inc., Mathematica, Version 9.0 (2012), Wolfram Research Inc.: Wolfram Research Inc. Champaign
[36] Xu, F.; Wong, D.; Tian, F. L., On the multiplicity of α as an eigenvalue of the \(A_\alpha\) matrix of a graph in terms of the number of pendant vertices, Linear Algebra Appl., 594, 193-204 (2020) · Zbl 1436.05067
[37] Xue, J.; Lin, H. Q.; Liu, S. T.; Shu, J. L., On the \(A_\alpha \)-spectral radius of a graph, Linear Algebra Appl., 550, 105-120 (2018) · Zbl 1385.05054
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.