A spectral excess theorem for normal digraphs

作者：Omidi G R^*

来源：Journal of Algebraic Combinatorics, 2015, 42(2): 537-554.

DOI：10.1007/s10801-015-0590-5

• The spectral excess theorem
• Weakly distance-regular digraphs
• Distance-regular digraphs
• 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 (generalization of the average excess) is, atmost, 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.

• 出版日期2015-9