Digraphs with real and gaussian spectra

Abstract

The conventional binary operations of cartesian product, conjunction, and composition of two digraphs D1 and D2 are observed to give the sum, the product, and a more complicated combination of the spectra of D1 and D2 as the resulting spectrum. These formulas for analyzing the spectrum of a digraph are utilized to construct for any positive integer n, a collection of n nonisomorphic strong regular nonsymmetric digraphs with real spectra. Further, an infinite collection of strong nonsymmetric digraphs with nonzero gaussian integer value is found. Finally, for any n, it is shown that there are n cospectral strong nonsymmetric digraphs with integral spectra.