A spectral excess theorem for normal digraphs

DOI10.1007/S10801-015-0590-5MaRDI QIDQ494302zbMATH OpenOpenAlexFDO

Authors G. R. Omidi

Publication date 31 August 2015

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.7382

zbMATH Keywords

spectral excess theoremdistance-regular digraphsnormal digraphsweakly distance-regular digraphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Association schemes, strongly regular graphs (05E30) Distance in graphs (05C12)

Abstract: It is known that every distance-regular digraph is connected and normal. An interesting question is: when is a given connected normal digraph distance-regular? Motivated by this question first we give some characterizations of weakly distance-regular digraphs. Specially we show that whether a given connected digraph to be weakly distance-regular only depends on the equality for two invariants. Then we show that a connected normal digraph $G$ with $d+1$ distinct eigenvalues is distance-regular if and only if the simple excess (the ratio of the square of mean of the numbers of shortest paths between vertices at distance $d$ to the mean of the numbers of vertices at distance $d$ from every vertex, which is zero if $d$ is greater than the diameter) is equal to the spectral excess (a number which can be computed from the spectrum of $G$). In fact, this result is a new variation (a simple variation) of the spectral excess theorem due to Fiol and Garigga for connected normal digraphs. Using these results we derive another variation (a weighted variation) of the spectral excess theorem for connected normal digraphs. Distance regularity of a digraph (also a graph) is in general not determined by its spectrum. For application of the simple variation we show that distance regularity of a connected normal digraph $G$ (with $d+1$ distinct eigenvalues) is determined by its spectrum and the invariant $delt{a}_d$ (the mean of the numbers of vertices at distance $d$ from every vertex). Finally as an application of the weighted variation we show that every connected normal digraph $G$ with $d+1$ distinct eigenvalues and diameter $D$ is either a bipartite digraph, or a generalized odd graph or it has odd-girth at most $min2d-1,2D+1$, generalizing a result of van Dam and Haemers and also a recent result of Lee and Weng.

Recommendations

• A spectral excess theorem for digraphs with normal Laplacian matrices
• A spectral excess theorem for nonregular graphs
• On a version of the spectral excess theorem
• On some approaches to the spectral excess theorem for nonregular graphs
• The Laplacian spectral excess theorem for distance-regular graphs

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• A directed graph version of strongly regular graphs
• A short proof of the odd-girth theorem
• A simple proof of the spectral excess theorem for distance-regular graphs
• A spectral excess theorem for nonregular graphs
• Algebraic characterizations of distance-regular graphs
• An odd characterization of the generalized odd graphs
• Certain distance-regular digraphs and related rings of characteristic 4
• Digraphs
• Distance-regular digraphs of girth 4
• Distance-transitive and distance-regular digraphs
• Dual concepts of almost distance-regularity and the spectral excess theorem
• Edge-distance-regular graphs
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• On almost distance-regular graphs
• On some approaches to the spectral excess theorem for nonregular graphs
• Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes
• Spectra of graphs
• Spectral characterization of odd graphs \(O_ k, k\leq 6\)
• Spectral characterization of some generalized odd graphs
• The spectral excess theorem for distance-regular graphs: a global (over)view
• Weakly distance-regular digraphs.

Cited in

(3)

• A spectral excess theorem for digraphs with normal Laplacian matrices
• A generalization of the odd-girth theorem
• On some approaches to the spectral excess theorem for nonregular graphs

This page was built for publication: A spectral excess theorem for normal digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494302)