A spectral excess theorem for normal digraphs
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). In 2012, Lee and Weng 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 Van Dam and Haemers.
normal digraphs the spectral excess theorem distance-regular digraphs weakly distance-regular digraphs 05c50 05e30