Shafiei, F. (2018). A spectral excess theorem for digraphs with normal Laplacian matrices. Transactions on Combinatorics, 7(3), 19-28. doi: 10.22108/toc.2018.105873.1513

Fateme Shafiei. "A spectral excess theorem for digraphs with normal Laplacian matrices". Transactions on Combinatorics, 7, 3, 2018, 19-28. doi: 10.22108/toc.2018.105873.1513

Shafiei, F. (2018). 'A spectral excess theorem for digraphs with normal Laplacian matrices', Transactions on Combinatorics, 7(3), pp. 19-28. doi: 10.22108/toc.2018.105873.1513

Shafiei, F. A spectral excess theorem for digraphs with normal Laplacian matrices. Transactions on Combinatorics, 2018; 7(3): 19-28. doi: 10.22108/toc.2018.105873.1513

A spectral excess theorem for digraphs with normal Laplacian matrices

The spectral excess theorem, due to Fiol and Garriga in 1997, is an important result, because it gives a good characterization of distance-regularity in graphs. Up to now, some authors have given some variations of this theorem. Motivated by this, we give the corresponding result by using the Laplacian spectrum for digraphs. We also illustrate this Laplacian spectral excess theorem for digraphs with few Laplacian eigenvalues and we show that any strongly connected and regular digraph that has normal Laplacian matrix with three distinct eigenvalues, is distance-regular. Hence such a digraph is strongly regular with girth $g=2$ or $g=3$.

[1] J. Bang-Jensen and G. Z. Gregory, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, 2nd ed, 2009.

[2] A. E. Brouwer, personal homepage: http://www.cwi.nl/~aeb/math/dsrg/dsrg.html.

[3] A. E. Brouwer, A. M. Cohen and A. Neumaier, distance-regular Graphs, Springer-Verlag, Berlin-New York, 1989.

[4] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2012; available online at http://homepages.cwi.nl/~aeb/math/ipm/.

[5] F. Comellas, M. A. Fiol, J. Gimbert and M. Mitjana, Weakly distance-regular digraphs, J. Combin. Theory Ser. B, 90 (2004) 233–255.

[6] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, VEB Deutscher Verlag der Wissenschaften, Berlin, second edition, 1982.

[7] C. Dalfo, E.R. Van Dam, M. A. Fiol and E. Garriga, Dual concepts of almost distance-regularity and the spectral excess theorem, Discrete Math., 312 (2012) 2730–2734.

[8] C. Dalfo, E. R. Van Dam, M. A. Fiol, E. Garriga and B. L. Gorissen, On almost distance-regular graphs, J. Combin. Theory Ser. A, 118 (2011) 1094–1113.

[9] R. M. Damerell, Distance-transitive and distance-regular digraphs, J. Combin. Theory Ser. B, 31 (1981) 46–53.

[10] A. M. Duval, A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A, 47 (1988) 71–100.

[11] E. R. Van Dam, The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., 15 (2008), pp. 10.

[12] E. R. Van Dam and M. A. Fiol, A short proof of the odd-girth theorem, Electron. J. Combin., 19 (2012) pp. 5.

[13] E. R. Van Dam and M. A. Fiol, The Laplacian Spectral Excess Theprem for distance-Regular Graphs, Linear Algebra Appl., 458 (2014) 1–6.

[14] Carl D. Meyer, Matrix analysis and applied linear algebra, Philadelphia, USA , 101 (2011) 486–489.

[15] M. A. Fiol, Algebraic characterizations of distance-regular graphs, Discrete Math., 246 (2002) 111–129.

[16] M. A. Fiol, On some approaches to the spectral excess theorem for nonregular graphs, J. Combin. Theory Ser. A, 120 (2013) 1285–1290.

[17] M. A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, 71 (1997) 162–183.

[18] M. A. Fiol, S. Gago and E. Garriga, A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., 432 (2010) 2418–2422.

[19] M. A. Fiol, E. Garriga and J. L. A. Yebra, Locally pseudo-distance-regular graphs, J. Combin.Theory Ser. B, 68 (1996) 179–205.

[20] G. S. Lee and C. W. Weng, The spectral excess theorem for general graphs, J. Combin. Theory Ser. A, 119 (2012) 1427–1431.

[21] G. R. Omidi, A spectral excess theorem for normal digraphs, J. Algebraic Combin., 42 (2015) 537–554.