A spectral excess theorem for normal digraphs

DOI10.1007/S10801-015-0590-5zbMATH Open1319.05062arXiv1310.7382OpenAlexW1989059090MaRDI QIDQ494302FDOQ494302

Authors: G. R. Omidi 

Publication date: 31 August 2015

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• A generalization of the odd-girth theorem
• A spectral excess theorem for digraphs with normal Laplacian matrices
• 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)