X
Non-singular circulant graphs and digraphs
Published in International Linear Algebra Society
2013
Volume: 26

Pages: 248 - 257
Abstract
For a fixed positive integer n, let Wn be the permutation matrix corresponding to permutation. In this article, it is shown that a symmetric matrix with rational entries is circulant if, and only if, it lies in the subalgebra of Q[x]/ (xn-1) generated by Wn+Wn -1. On the basis of this, the singularity of graphs on n-vertices is characterized algebraically. This characterization is then extended to characterize the singularity of directed circulant graphs. The kth power matrix Wnk+Wn -k defines a circulant graph Cnk. The results above are then applied to characterize its singularity, and that of its complement graph. The digraph Cr,s,t is defined as that whose adjacency matrix is circulant circ(a), where a is a vector with the first r-components equal to 1, and the next s, t and n - (r + s + t) components equal to zero, one, and zero respectively. The singularity of this digraph (graph), under certain conditions, is also shown to depend algebraically upon these parameters. A slight generalization of these graphs are also studied.