On Eigenvalues of Permutation Graphs

Document Type: Original Scientific Paper


Department of Mathematics, Faculty of Basic Sciences, Islamic Azad University, Central Tehran Branch, Tehran, Iran



Let λ1(G), λ2(G),..., λs(G) be the distinct eigenvalues of G with multiplicities t1, t2,..., ts, respectively. The multiset {λ1(G)t1, λ2(G)t2,..., λs(G)ts} of eigenvalues of A(G) is called the spectrum of G. For two graphs G and H, if their spectrum are the same, then G and H are said to be co-spectral. The aim of this paper is to determine co-spectral permutation graphs with respect to automorphism group of graph G.


[1] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. Henri
Poincaré 3 (1967) 433–438.
[2] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs–Theory and Application,
Academic Press, New York, 1980.
[3] A. W. Dudek, On the spectrum of the generalised Petersen graphs, Graphs
Combin. 32 (2016) 1843–1850.

[4] R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized
Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211–218.
[5] R. Gera and P. Stanica, The spectrum of generalized Petersen graphs, Australas.
J. Combin. 49 (2011) 39–45.
[6] C. Godsil and G. F. Royle, Algebraic Graph Theory, Springer, New York,
[7] P. D. Powell, Calculating determinants of block matrices, arXiv:1112.4379v1
[8] S. Saadat-Akhtar, S. Sahebi and M. Ghorbani, Co-spectrality of permutation
graphs, Ars Combin., in press.
[9] V. Yegnanarayanan, On some aspects of the generalized Petersen graph, Electron.
J. Graph Theory Appl. 5 (2017) 163–178.

Volume 4, Issue 2
Special Issue: Spectral Graph Theory and Mathematical Chemistry with Connection to Computer Science
Autumn 2019
Pages 319-325