Theoretical Statistics and Mathematics Unit, ISI Delhi

August 29, 2018 (Wednesday) ,
3:30 PM at Webinar

Speaker:
Gopinath Sahoo,
ISI Delhi

Title:
Complex adjacency spectra of (multi)digraphs

Abstract of Talk

Given any graph, we can uniquely associate a square matrix which stores informations about its vertices and how they are interconnected. The goal of spectral graph theory is to see how the eigenvalues and eigenvectors of such a matrix representation of a graph are related to the graph structure. In literature, there are a wide variety of matrices associated to a graph, such as the adjacency matrix, the Laplacian matrix, the normalized Laplacian matrix, etc. We consider here (multi)digraphs and their associated matrices only. Also, we define a new matrix representation for a multidigraph and named it as the complex adjacency matrix.

The relationship between the adjacency matrix and the complex adjacency matrix of a multidigraph are established. Further, some of the advantages of the complex adjacency matrix over the adjacency matrix of a multidigraph are observed. The complex adjacency eigensystems of many special families of multidigraphs (such as the path multidigraph, the cycle multidigraph, the star multidigraph, etc.) are obtained. Multidigraphs whose complex adjacency spectra are symmetric about origin are studied and some sufficient conditions of its occurrence are obtained. For a multi-directed tree it is proved that its complex adjacency spectrum is same as the adjacency spectrum of the corresponding modular tree.

Next, we consider operations on multidigraphs and determine the complex adjacency eigensystems of the resulting multidigraphs. Among some operations, we consider complement, join, corona and several product operations. As an application of corona operation, we get multidigraphs with the property that if $\lambda$ is a complex adjacency eigenvalue of a multidigraph, then $-\frac{1}{\lambda}$ is also a complex adjacency eigenvalue with the same multiplicity.

By a digraph, we mean a simple directed graph (i.e., if $(i,j)$ is an arc, then $(j,i)$ is not and no multiple arcs are allowed). As observed earlier, given a multi-directed tree if we change the direction of any multi-directed edge, then the complex adjacency spectrum remains unchanged. The same question can be asked for any multidigraph. If we change the direction of some arc, how will it affect the spectrum? Considering the classes of some special digraphs (such as path digraphs, star digraphs, generalized star digraphs, flower digraphs, wheel digraphs, lattice digraphs, etc.), we try to answer the question. Further, it is shown that not only the complex adjacency eigenvalues but also their corresponding eigenvectors carry information about the structure of the digraphs.