Computing the spectrum of L^t(G) for a regular graph

Document Type : Research Paper


Department of Mathematics, Faculty of Mathematics, Statistics and Computer Sciences, Semnan University, Semnan, Iran.


If L(G) is the line graph of G, it is difficult to get the adjacency matrix of Lt(G)=L(L(L ... L(G))); t≥3 and also its spectrum. In this paper, we present a formula to compute the spectrum of Lt(G), for each positive integer t, where G is a regular graph.


1.N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge (1974).
2. L. Branković, D. Cvetković, The eigenspace of the eigenvalue -2 in generalized line graphs and a problem in security of statistical databases, Univ. Beograd. Publ. ektrotehn. Fak. Ser. Mat., 14, 37–48 (2003).
3. A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York (2012).
4. D. Cvetkovic, P. Rowlinson, S. Simic, Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2, Cambridge University Press, Cambridge (2004).
5. K. Ch. Das, S. A. Mojallal, I. Gutman, On energy of line graphs, Linear Algebra Appl., 499, 79–89 (2016).
6. A. J. Hoffman, Eigenvalues and partitionings of the edges of a graph, Linear Algebra Appl., 5, 137–146 (1972).
7. H. Sachs, Ü. Teiler, Faktoren und characterische Polynome von Graphen II., Wiss. Z. Techn. Hosch. Ilmenau, 13, 405–412 (1967).
8. J. J. Seidel, Strongly regular graphs with (−1, 1, 0) adjacency matrix having eigenvalue 3, Linear Algebra Appl., 1, 281–298 (1968).
9. S. G. Suresh, Graph Theory, PHI Learning Pvt. Ltd, (2010).
10. D. B. West, Introduction to Graph Theory, New Jersey (2001).
11. T. Zaslavsky, Line Graphs Eigenvalues and Root Systems, State University of New York, New York (2010).