Published Paper "The Inverse Characteristic Polynomial Problem for Graphs over Finite Fields"

Book Title

Recent Research in Polynomials

Publication Information

• Chapter Title: The Inverse Characteristic Polynomial Problem for Graphs over Finite Fields
• ISBN: 978-1-83769-496-9
• Submitted: December 14th, 2022
• Reviewed: February 3rd, 2023
• Published: April 13th, 2023
• DOI: 10.5772/intechopen.1001164

Abstract

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.

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.