Article ID Journal Published Year Pages File Type
6416689 Linear Algebra and its Applications 2013 16 Pages PDF
Abstract

Let G be a graph and A(G) the adjacency matrix of G. The permanental polynomial of G is defined as π(G,x)≜per(xI-A(G)). If two graphs G and H have the same permanental polynomial, then G is called a per-cospectral mate of H. A graph G is said to be characterized by its permanental polynomial if all the per-cospectral mates of G are isomorphic to G. It is shown that complete graphs, stars, regular complete bipartite graphs, and odd cycles are characterized by their permanental polynomials. We prove that in general the permanental polynomial cannot characterize the paths and even cycles. In particular, for each l⩾1 and m⩾2, we can find non-isomorphic per-cospectral mates of P4l+3 and C4m, respectively. When we restrict our consideration to connected graphs, both the paths and even cycles C4l+2 are characterized by their permanental polynomials.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
, ,