卢鹏丽，武雨末

（兰州理工大学计算机与通信学院，甘肃兰州730050）

广义剖分冠点图的邻接特征多项式

卢鹏丽，武雨末

（兰州理工大学计算机与通信学院，甘肃兰州730050）

冠图是由图G与图H经过图操作得到的组合图，已经有一些冠图被定义及研究。但是现有文献中的冠图定义均是将图H进行n次拷贝，得到的图G与图H的各类冠图。将冠图的定义推广为一般化的情形，即将原来n个相同的图H一般化为任意图H1，H2，…，Hn，定义了一类新的广义剖分冠点图。首先在图G的每条边上添加一个新的顶点得到其剖分图S（G）；将V（G）中的第i个顶点与Hi中的所有顶点连接；这样由剖分图S（G）和图H1， H2，…，Hn构造的图称为广义剖分冠点图，记为图应用分块矩阵、矩阵的冠、舒尔补定理等确定了广义剖分冠点图的邻接特征多项式；提出了构造无穷邻接同谱图类的方法且给出了示例。

组合图；广义剖分冠点图；邻接特征多项式；正则图；同谱图

本文只讨论无向简单图。图G= (V（G），E（G）)，其中顶点集和边集分别为V（G）=｛v1，v2，…，vn｝， E（G）=｛e1，e2，…，em｝图G的邻接矩阵记为A（G），由元素aij组成，当顶点vi与vj相邻时为1，否则为0。图G的关联矩阵记为R（G），是由元素bij组成，当顶点vi与边ej相邻时为1，否则为0。顶点vi的度记为dG（i）。图G的度矩阵记为D（G），是对角线上元素为dG（i）的n× n对角矩阵。并且有R（G）R（G）T=A（G）+ D（G）。图G的邻接特征多项式记为

式中:In表示大小为n的单位矩阵。由邻接特征多项式得到的特征值称为邻接特征值，从大到小排序为λn≥λn-1≥…≥λ2≥λ1。拥有相同邻接特征多项式的图叫做A-同谱图［1-3］。

冠图是由两个图，图G与图H经过图操作得到的复杂图。……