On the spectrum of 3-coloured digraphs

Abstract

The notion of a 3-coloured digraph introduced in Bapat et al. [R.B. Bapat, D. Kalita, and S. Pati, On weighted directed graphs, Linear Algebra Appl. (2011), In press, doi:10.1016/j.laa.2011.06.035] is a generalization of the mixed graphs. In this article, we study the adjacency and the Laplacian spectra of 3-coloured digraphs. Our main objective is to investigate whether the adjacency (resp. Laplacian) spectrum of a 3-coloured digraph can be realized as a subset of the adjacency (resp. Laplacian) spectrum of a suitable undirected graph. In order to achieve this, some graph operations similar to that in Fan [Y.Z. Fan, On eigenvectors of mixed graphs with exactly one nonsingular cycle, Czech. Math. J. 57 (2007), pp. 1215–1222] are introduced. Using these graph operations, we show that for a connected 3-coloured digraph on n vertices, there exists a mixed graph on 2n vertices whose adjacency and Laplacian eigenvalues are precisely those of the 3-coloured digraph with doubled multiplicities. We also show that for a connected mixed graph G on n vertices, there is an unweighted undirected graph H on 2n vertices whose adjacency (resp. Laplacian) spectrum contains the adjacency (resp. Laplacian) spectrum of the mixed graph. We also supply a description of the remaining adjacency (resp. Laplacian) eigenvalues of H. Finally, we describe the adjacency and Laplacian spectrum of a class of unweighted undirected graphs of which H is a particular member.

Keywords:

• Laplacian matrix
• mixed graph
• weighted directed graph
• 3-coloured digraph

AMS Subject Classifications::

• 05C50
• 05C05
• 15A18

Acknowledgements

The authors sincerely thank the referees and the editors for their valuable suggestions. The financial assistance for D. Kalita was provided by CSIR, India, through a SRF.