完全图删六条边所得的图由第二 Immanantal 多项式确定-《集美大学学报（自然科学版）》

文章信息/Info

Title:: All Graphs Obtained by Removing Six Edges from a Complete Graph Are Determined by the Second Immanantal Polynomials

Author(s):: GENG Yafan; WU Tingzeng; (School of Mathematics and Statistics，Qinghai Minzu University，Xining 810007，China)

Keywords:: Laplacian matrix; second Immanant; second Immanantal polynomial; cospectral graphs

摘要:: 图的多项式刻画问题是图谱理论中的一个经典问题。令G是有n个顶点的图，L(G)表示图G的拉普拉斯矩阵，I表示n阶单位矩阵。称d2(xI-L(G))为图G的第二Immanantal多项式。Merris研究了正则图的第二Immanantal多项式刻画问题，但是关于非正则图的第二Immanantal多项式刻画问题的结果还比较少。通过比较完全图删六条边所得的图的生成树数目，以及图G的第二Immanantal多项式的系数，证明了完全图删除六条边所得的图是由第二Immanantal多项式确定的。

Abstract:: Let G be a graph with n vertices,and let L(G) denote the Laplacian matrix of G.The polynomial d2(xI-L(G)) is called the second Immanantal polynomial of G,where I denotes the unit matrix of order n.The problem which graphs are determined by their polynomials is a classic question in spectral theory,which has been widely studied.Merris has studied the second Immanantal polynomial characterization problem of regular graphs,but there are relatively few results on the problem of characterizing the second Immanantal polynomial of nonregular graphs.In this paper,we compare the number of spanning trees of graphs obtained by removing six edges from a complete graph and study the coefficients of the second Immanantal polynomial in the graph G,and we show that graphs obtained from a complete graph by removing six edges are determined by their second Immanantal polynomials.