图多项式以及图的不同特征根个数

POLYNOMIALS ON GRAPH AND THE NUMBER OF DISTINCT EIGENVALUES OF GRAPHS

设G是具有邻接矩阵A的简单图,P(x)是有理系数多项式,如果P(A)是某个图的邻接矩阵,我们记这个图为P(G)。我们考虑这样的问题:给一个图G,什么样的多项式P(x)给出一个图P(G)?这个图是什么样的图?当G是星图时,本文对上述问题给出完全的回答。然后,还导出一个连通正则图的不同特征根个数的新的下界。

Let G be a simple graph with adjacency matrrx A. and p(x) a polynomral with rational coefficients. If p ( A ) is the adjacency matrix of a graph, we denote that graph by p(G). We consider the question. Given a graph G, which polynomials p(x) give rise to a graph p(G) and what are those graphs? We give a complete answer if G is a Star graph. We then derive a new lower bound for the number of distinct eigenvalues of a regular connected graph.