一类G与G相交于一点的图的特征值.pdfVIP

2007年11月 绵阳师范学院学报 Nov．，2007 26卷 第 11 Journal of Mianvan~t Normal Univ V01．26 No．11 一 类G与G相交于一点的图的特征值 任秋道 (绵阳师范学院数学与信息科学系，四川绵阳 621000) 摘 要：图G的特征值是图的一个重要不变量。在量子化学和理论化学中有大量的应用。当图G的顶点数 较大时，其邻接矩阵的阶数较大，计算特征值较困难。分块降阶是通常的方法。本文针对一些特殊图的邻接矩阵 进行分块降阶求特征值。如果在 (G)上有一个一一映射 ，使得 ( )= 一 ， =1，2，…，，l，那么G的点 。仅与 G的点 ，重合的图G+G的特征值中有G— 的特征值。 关键词：邻接矩阵；特征值；映射 中图分类号：O175 文献标识码：A 文章编号：1672-612x(2007)11-0014-04 l 51人 图G是I／,个顶点简单连通图，A是图G的邻接矩阵。A的特征值称为图G的特征值。行列式I AE—A J称 为图G的特征多项式，记作 (G)。A是对称矩阵，其特征值都是实数。A的全体特征值称为图G的谱。图G的 特征值是图一个重要不变量。在量子化学和理论化学中有大量的应用。自从1950年以后，对图G的特征值 有了大量的研究，有很多重要的结论…[2】。现在，循环图的特征值是完全清楚的…，树的特征值有许多重要 的结果 儿 。设图G的顶点集 (G)= ， ：，… }。如果在 (G)上有一个一一映射 ，使得 (1)i)= 。，i=1，2，…，n。这个映射 就是本文所指的映射。讨论了图G的点 。与G的点 重合的图G+G的特 征值情况。需要用到的主要结论： 引理1．1¨ 完全图K的谱specK =f乃=-、 l 一 ．1。 I／,一 l／ 引理1。2 设U1)是图G的悬挂边，顶点 的度是1。则图G的特征多项式 (G)=A (G一 )一 (G 一 一 U)o 2 G+G的特征值 设图G的顶点集 (G)= ， ：，… }。图G的邻接矩阵 A=(a{f) …其中a =1当且仅当点 与 f相邻，否则a =0。 引理2．1 设在 (G)上有一个一一映射 ，G的邻接矩阵为A=(a ) 。则有a =a 巾。，f，_『=1，2， … I／,o ， 证明：由于 ( )= 。， =1，2，…，I／,。顶点 。， ：，…， 的象分别是 ， 一 一， 。。a 也表示顶点 。 与顶点 ，的邻接的情况，表示顶点 。与顶点 巾。的邻接的情况。因此，a =a 巾。， J=1，2， … ， n。结论成立。 0 0 … 1 0 0 … 0 推论：设I／,阶矩阵P= 。 则A=PAP。 0 1 … 0 1 0 … 0 G的点 。仅与G的点 重合的图，简记为G+G。在映射 作用下， 。与 等价，G+G也就是G的点 。仅与G的点 。重合的图。如图1。G一 。的邻接矩阵A 与G一 的邻接矩阵A 相似。事实上，从G一13。的 顶点集{ ：， ，，… }到G一 的顶点集 ， ：，… 一。}有一个一一映射 ，使得O(V )= +．，i=2，3，…， 收稿日期：2007-04—11 作者简介：任秋道(1965一 )，男，硕士，讲师．主要研究方向：图论与组合。 第11期 任秋道：一类C与C相交于一点的图的特征值 ·15·