On relation between spectra of graphs and their digraph decompositions. (English) Zbl 1224.05322

Let \(G\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). Each undirected edge may be alternatively viewed as a pair of oppositely oriented directed edges and the whole undirected graph \(G\) may be decomposed into a pair of digraphs, \(\overrightarrow{G}\) and \(\overleftarrow{G}\), consisting of oppositely oriented directed edges, such that \(V(\overrightarrow{G})=V(\overleftarrow{G})=V(G)\) and \(E(G)=E(\overrightarrow{G})\cup E(\overleftarrow{G})\).
The spectrum of a digraph \(\overrightarrow{G}\) is a collection of eigenvalues of its adjacency matrix \(A(\overrightarrow{G})\). The adjacency matrix \(A(\overrightarrow{G})\) is the transpose of \(A(\overleftarrow{G})\) and the digraphs \(\overrightarrow{G}\) and \(\overleftarrow{G}\) have equal spectra. For annulenes, undirected cycles, the eigenvalue spectrum of the graph is equal to the sum of the eigenvalue spectra of respective two digraphs. In general, the eigenvalues of an undirected graph \(G\) are not related to the eigenvalues of digraphs from its digraph decomposition. In this paper, a number of other graphs with this property is presented.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI