The Inverse Characteristic Polynomial Problem for Graphs over Finite Fields

Let \(\mathbb{F}\) be a finite field, and let \(G\) be a graph on \(n\) vertices. We study the possible characteristic polynomials that may be realized by matrices \(A\) over a finite field such that the graph of \(A\) is \(G\). We focus mainly on the case \(G\) is a tree \(T\), not only because trees are computationally simpler, but also because the theory of eigenvalue multiplicities is much better understood for trees than it is for general graphs. We demonstrate the applications to this problem by branch duplication and the recently developed geometric Parter–Wiener, etc. theory. We end with a list of several conjectures which should pave the way for future study.

Recommended citation: C. Johnson, X. Lin, X. Liu, G. Wesley, and S. Zhou. "The Inverse Characteristic Polynomial Problem for Graphs over Finite Fields". In: F. Ozger (Ed.), Recent Research in Polynomials (2023), Chapter 6.
Download Paper