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 ($ \mathrm{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 $ \mathrm{DGQS} $ graphs by considering the rooted product graphs $ G\circ P_{k} $. They proved that when $ k = 2, 3 $, $ G\circ P_{k} $ is $ \mathrm{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 $ \mathrm{DGQS} $ property for $ G\circ P_{k} $.
Citation: Liwen Gao. A new approach for constructing the graphs determined by their generalized $ Q $-spectrum[J]. Electronic Research Archive, 2026, 34(2): 821-829. doi: 10.3934/era.2026037
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 ($ \mathrm{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 $ \mathrm{DGQS} $ graphs by considering the rooted product graphs $ G\circ P_{k} $. They proved that when $ k = 2, 3 $, $ G\circ P_{k} $ is $ \mathrm{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 $ \mathrm{DGQS} $ property for $ G\circ P_{k} $.
| [1] |
H. H. G$\ddot{u}$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 doi: 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 doi: 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 doi: 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 doi: 10.1016/j.jctb.2016.07.004
|
| [5] |
D. M. Cvetkovć, 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 doi: 10.2298/PIM0999019C
|
| [6] |
D. M. Cvetković, S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian Ⅱ, Linear Algebra Appl., 432 (2010), 2257–2272. https://doi.org/10.1016/j.laa.2009.05.020 doi: 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 Ⅲ, Appl. Anal. Discrete Math., 4 (2010), 156–166. https://doi.org/10.2298/AADM1000001C doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 10.13001/1081-3810.3298
|
Liwen Gao. A new approach for constructing the graphs determined by their generalized $ Q $-spectrum[J]. Electronic Research Archive, 2026, 34(2): 821-829. doi: 10.3934/era.2026037
DownLoad: