×

Generalized spectral characterization of mixed graphs. (English) Zbl 1472.05102

A mixed graph \(G\) is said to be strongly determined by its generalized Hermitian spectrum (abbreviated SHDGS), if, up to isomorphism, \(G\) is the unique mixed graph that is cospectral with \(G\) w.r.t. the generalized Hermitian spectrum. The authors conjecture that every such graph is SHDGS and prove that, for any mixed graph \(H\) that is cospectral with \(G\) w.r.t. the generalized Hermitian spectrum, there exists a Gaussian rational unitary matrix \(U\) with \(Ue = e\) such that \(U^\ast A(G)U = A(H)\) and \((1+i)U\) is a Gaussian integral matrix. The authors verify the conjecture in two extremal cases when \(G\) is either an undirected graph or a self-converse oriented graph. Consequently, the authors prove that all directed paths of even order are SHDGS.

MathOverflow Questions:

An equality about sin function?

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

References:

[1] S. Akbari, A. Ghafaria, M. Nahvib, M. A. Nematollahia, Mixed paths and cycles determined by their spectrum,Linear Algebra Appl., 586 (2020) 325-346. · Zbl 1429.05117
[2] B. Mohar, Hermitian adjacency spectrum and switching equivalence of mixed graphs, Linear Algebra Appl., 489 (2016) 324-340. · Zbl 1327.05215
[3] E. R. van Dam, W. H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl., 373 (2003) 241-272. · Zbl 1026.05079
[4] E. R. van Dam, W. H. Haemers, Developments on spectral characterizations of graphs,Discrete Math., 309 (2009) 576-586. · Zbl 1205.05156
[5] K. Guo, B. Mohar, Hermitian adjacency matrix of digraphs and mixed graphs,J. Graph Theory, 85(1) (2017) 324-340. · Zbl 1365.05173
[6] C. R. Johnson, M. Newman, A note on cospectral graphs,J. Combin. Theory, Ser. B, 28 (1980) 96-103. · Zbl 0431.05021
[7] J. Liu, X. Li, Hermitian-adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl., 466 (2015) 182-207. · Zbl 1302.05106
[8] L. Mao, F. Liu, W. Wang, A new method for constructing graphs determined by their generalized spectrum,Linear Algebra Appl., 477(15) (2015) 112-127. · Zbl 1311.05117
[9] B. D. Makay, A. Piperno, Practical graph isomorphism, II,J. Symb. Comput., 60 (2014) 94-112. · Zbl 1394.05079
[10] https://mathoverflow.net/questions/338274/an-equality-about-sin-function. [Accessed on 7th March, 2020.]
[11] L. Qiu, Y. Ji, W. Wang, A new arithmetic criterion for graphs being determined by their generalizedQ-spectrum,Discrete Math., 342 (2019) 2770-2782. · Zbl 1417.05123
[12] L. Qiu, Y. Ji, W. Wang, On the generalized spectral characterizations of Eulerian graphs,Electron. J. Combin.,26(1) (2019) #P9. · Zbl 1409.05130
[13] SageMath, the Sage Mathematics Software System (Version 8.9),The Sage Developers, 2019,https://www.sagemath.org.
[14] K. Tran, Discriminants of polynomials related to Chebyshev polynomials: The “Mutt and Jeff” syndrome.J. Math. Anal. Appl., 383(1)(2011) 120-129. · Zbl 1232.33020
[15] W. Wang, Generalized spectral characterization revisited,Electron. J. Combin., 20(4) (2013) #P4. · Zbl 1298.05214
[16] W. Wang,On the spectral characterization of graphs, PhD Thesis, Xi’an Jiaotong University, 2006 (in Chinese).
[17] W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra,J. Combin. Theory, Ser. B, 122 (2017) 438-451. · Zbl 1350.05098
[18] 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. · Zbl 1105.05050
[19] W. Wang, C.-X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra,European J. Combin., 27 (2006) 826-840. · Zbl 1092.05050
[20] P.
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.