Back to Homepage
Research Interests
Publications
Spectral Graph Theory
Cospectral Graphs. Let us call the multiset of eigenvalues of the adjacency matrix associated with a graph as the graph spectrum. Two graphs are cospectral if they have the same spectrum. While two isomorphic graphs are necessarily cospectral, the converse is not always true, and therefore the graph spectrum is not a complete graph invariant. However, it may still be a useful graph invariant towards solving graph isomorphism problem. A graph is said to be DS (determined by its spectrum) if every graph that is cospectral to it is also isomorphic. An important conjecture in this direction is that "almost all graphs are DS". To produce evidence against this conjecture, one may study various techinques to construct cospectral nonisomorphic graphs. We studied two techniques, unfolding and the partitioned tensor product, and discovered they have a connection.
Permanental Polynomial. The spectrum of a graph is also the multiset of roots of the characteristic polynomial of the adjacency matrix. While the characteristic polynomial is a central object of study in spectral graph theory, the permanental polynomial, which is obtained by simply replacing the determinant function with the permanent, is less understood as a graph invariant in comparison. One can study the permanental polynomial via its roots or in relation with the characteristic polynomial. An open problem in this direction is to characterize graphs all of whose permanental polynomial roots are purely imaginary. We construct some new graphs with this property. The permanent is known for its computational hardness. We also give an expression to compute the permanental polynomial using only the characteristic polynomial for a special class of graphs.