图的谱矩公式研究

吴亚平，付捷

（江汉大学数学与计算机科学学院，湖北武汉430056）

图的谱矩公式研究

吴亚平，付捷

（江汉大学数学与计算机科学学院，湖北武汉430056）

重构猜想的研究中涉及的一个问题是找出图不变量的完全组。由于图的第k阶谱矩等于图中长为k的闭途径的条数，可知谱矩序列是图的一个重要不变量。通过研究图的结构特征，首先确定能生成长为8的闭途径的所有子图，然后给出图的第8阶谱矩计算公式。

邻接矩阵；第k阶谱矩；星树；单圈图；双圈图

0 引言

1942年Kelly和Ulam［1］提出重构猜想，重构猜想是图论中至今尚未解决的三大难题之一。找出图不变量的完全组，即找出可以完全确定一个图的一组参数，是重构猜想研究中涉及的一个重要问题。目前，图不变量的完全组仍未确定。已研究的重要参数有：点连通度、边连通度、独立数、色数、最长路长、围长、周长、最大匹配数、度序列等等。图的第k阶谱矩等于图中长为k的闭途径的条数，可知谱矩序列是图的一个重要不变量。因此图的第k阶谱矩计算公式的确定对研究重构猜想是有意义的。

猜想［1］（重构猜想）如果G是至少有三个顶点的简单图，则G由它的顶点删除子图（的同构类）序列唯一确定。

1987年Cvetkovíc和Rowlinson[2]证明了图的第1～4阶谱矩的计算公式，并分别给出树和单圈图谱矩序最小和最大的图。2009年范琼和吴亚平[3]给出图的第5阶和第6阶谱矩的计算公式。2012年吴亚平等[4]给出树的第8阶谱矩计算公式。2013年吴亚平等[5]给出图的第7阶谱矩计算公式。近些年，谱矩吸引了越来越多人研究［6-14］。……