A new approach for constructing the graphs determined by their generalized Q-spectrum

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

We define the adjacency matrix A(G) and the degree diagonal matrix D(G) for a graph G. The Q-spectrum is the multiset of eigenvalues of the Q-matrix Q(G) = A(G) + D(G), counted with their algebraic multiplicities. A class of graphs is determined by their generalized Q-spectrum (DGQS for short) if any two graphs in the class have the same Q-spectrum and so do their complements, implying that they are isomorphic. Tian et al. introduced a new method to construct DGQS graphs by considering the rooted product graphs G ◦ Pk. They proved that when k = 2, 3, G ◦ Pk is DGQS for a special class of graphs G. In this paper, we extend this result and prove that, under the same conditions for G, the conclusion holds true for any positive integer k. While Wang et al. reported comparable results, our study arrives at these findings through an entirely different methodology. Our proof adopts the elementary properties of the resultants, providing an innovative approach to establishing the DGQS property for G ◦ Pk.

Keywords

graph spectrum / rooted product graphs / Q-matrix / resultants / determined by their generalized Q-spectrum

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] H. H. Güntard, H. Primas, Zusammenhang von Graphenteorie und MO-Theorie von Molekeln mit Systemen konjugierter, Helv. Chim. Acta, 39 (1956), 1645-1653. https://doi.org/10.1002/hlca.19560390623

[2] W. Wang, C. X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, Eur. J. Comb., 27 (2006), 826-840. https://doi.org/10.1016/j.ejc.2005.05.004

[3] W. Wang, C. X. Xu, An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra, Linear Algebra Appl., 418 (2006), 62-74. https://doi.org/10.1016/j.laa.2006.01.016

[4] W. Wang, A simple arithmetic criterion for graphs being determined by by their generalized spectra, J. Comb. Theory Ser. B, 122 (2017), 438-451. https://doi.org/10.1016/j.jctb.2016.07.004

[5] D. M. Cvetković, S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian, Publ. Inst. Math., 85 (2009), 19-33. https://doi.org/10.2298/PIM0999019C

[6] D. M. Cvetković, S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian II, Linear Algebra Appl., 432 (2010), 2257-2272. https://doi.org/10.1016/j.laa.2009.05.020

[7] D. M. Cvetković, S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian III, Appl. Anal. Discrete Math., 4 (2010), 156-166. https://doi.org/10.2298/AADM1000001C

[8] G. R. Omidi, On a signless Laplacian spectral characterization of T-shape trees, Linear Algebra Appl., 431 (2009), 1607-1615. https://doi.org/10.1016/j.laa.2009.05.035

[9] A. Schrijver, The Theory of Linear and Integer Programming, John Wiley & Sons, 1998.

[10] L. Qiu, Y. Ji, W. Wang, A new arithmetic criterion for graphs being determined by their generalized Q-spectrum, Discrete Math., 342 (2019), 2770-2782. https://doi.org/10.1016/j.disc.2018.08.008

[11] C. D. Godsil, B. D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc., 18 (1978), 21-28. https://doi.org/10.1017/S0004972700007760

[12] G. X. Tian, J. X. Wu, S. Y. Cui, H. L. Sun, Construction of graphs being determined by their generalized Q-spectra, preprint, arxiv: 2307.14832.

[13] Z. D. Yan, L. H. Mao, W. Wang, On the determinant of the Q-walk matrix of rooted product with a path, Bull. Malays. Math. Sci. Soc., 47 (2024), 174. https://doi.org/10.1007/s40840-024-01774-5

[14] Z. Z. Lou, Q. X. Huang, X. Y. Huang, On the construction of Q-controllable graphs, Electron. J. Linear Algebra, 32 (2017), 365-379. https://doi.org/10.13001/1081-3810.3298