Get all the updates for this publication

Articles

Non-singular circulant graphs and digraphsOpen Access

Published in International Linear Algebra Society

2013

Volume: 26

Pages: 248 - 257

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.

Topics: Circulant graph (65)%65% related to the paper, Circulant matrix (63)%63% related to the paper, Complement graph (62)%62% related to the paper, Adjacency matrix (62)%62% related to the paper and Permutation matrix (54)%54% related to the paper

View more info for "Non-singular circulant graphs and digraphs"

Preprint Version

Content may be subject to copyright.This is a green open access article.This is a green open access article.

About the journal

Published in International Linear Algebra Society

Open Access

yesImpact factor

N/A