Title

A disrespectful polynomial

Document Type

Article

Publication Date

1990

Publication Title

Linear Algebra and Its Applications

Department

Mathematics and Computer Science

Abstract

Given a graph and a polynomial, a matrix can be constructed by evaluating the polynomial with the adjacency matrix of the graph. When will the resulting matrix be the adjacency matrix of another graph? We answer this question for orbit polynomial graphs. We then investigate a conjecture of Weichsel relating the automorphism groups and eigenvalues of a graph G and another graph generated from G by a polynomial. For vertex-transitive graphs with a prime number of vertices the conjecture is true, but we also provide examples where it is false.

Volume

128

pp.

139-146

ISSN

0024-3795