×

zbMATH — the first resource for mathematics

New families of graphs determined by their generalized spectrum. (English) Zbl 1405.05105
Summary: We construct infinite families of graphs that are determined by their generalized spectrum. This construction is based on new formulae for the determinant of the walk matrix of a graph. All graphs constructed here satisfy a certain extremal divisibility condition for the determinant of their walk matrix.
MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Cámara, M.; Haemers, W. H., Spectral characterizations of almost complete graphs, Discrete Appl. Math., 176, 19-23, (2014) · Zbl 1298.05233
[2] Cvetković, D. M.; Petrić, M., A table of connected graphs on six vertices, Discrete Math., 50, 37-49, (1984) · Zbl 0533.05052
[3] Cvetković, D. M.; Rowlinson, P.; Simić, S. K., An Introduction to the Theory of Graph Spectra, (2010), Cambridge University Press: Cambridge University Press Cambridge
[4] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum, Linear Algebra Appl., 373, 241-272, (2003) · Zbl 1026.05079
[5] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586, (2009) · Zbl 1205.05156
[6] C.D. Godsil, Are almost all graphs determined by their spectrum? https://pdfs.semanticscholar.org/presentation/6b04/5c86e2212ac72e2e80024b025d76bf52c72d.pdf.
[7] Godsil, C. D., Controllable subsets in graphs, Ann. Comb., 16, 733-744, (2012) · Zbl 1256.05139
[8] Godsil, C. D.; Royle, G., Algebraic Graph Theory, (2001), Springer-Verlag: Springer-Verlag New York
[9] W.H. Haemers, Are almost all graphs determined by their spectrum? http://members.upc.nl/w.haemers/sams.pdf. · Zbl 1026.05079
[10] Hatice, T.; Sorgun, S., The kite graph is determined by its adjacency spectrum, Appl. Math. Comput., 330, 134-142, (2018)
[11] Hatice, T.; Sorgun, S.; Haemers, W. H., On the spectral characterization of pineapple graphs, Linear Algebra Appl., 507, 267-273, (2016) · Zbl 1343.05098
[12] He, C. X.; van Dam, E. R., Laplacian spectral characterization of roses, Linear Algebra Appl., 536, 19-30, (2018) · Zbl 1372.05128
[13] 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
[14] O’Rourke, S.; Touri, B., On a conjecture of Godsil concerning controllable random graphs, Siam J. Control Optim., 54, 3347-3378, (2016) · Zbl 1352.93027
[15] Rowlinson, P., The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1, 445-471, (2007) · Zbl 1199.05241
[16] Sciriha, I., A characterization of singular graphs, Electron. J. Linear Algebra, 16, 451-462, (2007) · Zbl 1142.05344
[17] Siemons, J.; Zalesski, A., Remarks on singular Cayley graphs and vanishing elements of simple groups, J. Algebraic Combin., (2018), arXiv:180401204
[18] Wang, W., Generalized spectral characterization revisited, Electron. J. Combin., 20, 4, # P4, (2013) · Zbl 1298.05214
[19] Wang, W., A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Combin. Theory Ser. B, 122, 438-451, (2017) · Zbl 1350.05098
[20] Wang, W.; Xu, C. X., A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin., 27, 826-840, (2006) · Zbl 1092.05050
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.