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

Stevanović, Dragan; Stevanović, Sanja

Publ. Inst. Math., Nouv. Sér. 85(99), 47-54 (2009).

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.

Reviewer: Olga Miljković (Beograd)

MSC:

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

Keywords:

graph spectrum; oppositely oriented directed edges; annulenes; undirected cycles; digraphs