A spectral excess theorem for normal digraphs
Journal of Algebraic Combinatorics, Tome 42 (2015) no. 2, pp. 537-554.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

The spectral excess theorem, a remarkable result due to Fiol and Garriga, states that a connected regular graph with $d+1$ distinct eigenvalues is distance-regular if and only if the average excess (the mean of the numbers of vertices at distance $d$ from every vertex) is equal to the spectral excess (a number that only depends on the spectrum of the graph). G. S. Lee and C. W. Weng [J. Comb. Theory, Ser. A 119, No. 7, 142--1431 (2012; Zbl 1245.05087)] gave a generalization of this result in order to make it applicable to non-regular graphs. Up to now, there has been no such characterization for distance-regular digraphs. Motivated by this, we give a variation of the spectral excess theorem for normal digraphs (which is called "SETND" for short), generalizing the above-mentioned results for graphs. We show that the average weighted excess (a generalization of the average excess) is, at most, the spectral excess in a connected normal digraph, with equality if and only if the digraph is distance-regular. To state this, we give some characterizations of weakly distance-regular digraphs. Particularly, we show that whether a given connected digraph is weakly distance-regular only depends on the equality of the two invariants. Distance-regularity of a digraph (also a graph) is in general not determined by its spectrum. As an application of SETND, we show that distance-regularity of a connected normal digraph is determined by the spectrum and the average excess of the digraph. Finally, as another application of SETND, we show that every connected normal digraph $\Gamma $ with $d+1$ distinct eigenvalues and diameter $D$ either is a bipartite digraph, is a generalized odd graph or has odd-girth at most $\min \{2d-1,2D+1\}$. This generalizes a result of E. R. van Dam and W. H. Haemers [J. Comb. Theory, Ser. B 101, No. 6, 486--489 (2011; Zbl 1234.05157)].
Classification : 05C20, 05C12, 05C50, 05E30
Keywords: spectral excess theorem, weakly distance-regular digraphs, distance-regular digraphs, normal digraphs
@article{JAC_2015__42_2_a4,
     author = {Omidi, G. R.},
     title = {A spectral excess theorem for normal digraphs},
     journal = {Journal of Algebraic Combinatorics},
     pages = {537--554},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2015__42_2_a4/}
}
TY  - JOUR
AU  - Omidi, G. R.
TI  - A spectral excess theorem for normal digraphs
JO  - Journal of Algebraic Combinatorics
PY  - 2015
SP  - 537
EP  - 554
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2015__42_2_a4/
LA  - en
ID  - JAC_2015__42_2_a4
ER  - 
%0 Journal Article
%A Omidi, G. R.
%T A spectral excess theorem for normal digraphs
%J Journal of Algebraic Combinatorics
%D 2015
%P 537-554
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2015__42_2_a4/
%G en
%F JAC_2015__42_2_a4
Omidi, G. R. A spectral excess theorem for normal digraphs. Journal of Algebraic Combinatorics, Tome 42 (2015) no. 2, pp. 537-554. http://geodesic.mathdoc.fr/item/JAC_2015__42_2_a4/