A spectral excess theorem for digraphs with normal Laplacian matrices

Document Type : Research Paper

Author

Isfahan University of Technology

Abstract

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$‎.

Keywords

Main Subjects

References

[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.
Transactions on Combinatorics
Volume 7, Issue 3 - Serial Number 3
September 2018
Pages 19-28

Files

History

  • Receive Date: 11 August 2017
  • Revise Date: 10 January 2018
  • Accept Date: 11 January 2018
  • Published Online: 01 September 2018

Share

How to cite

Statistics