论文部分内容阅读
图的谱确定性理论是图论中的一个新兴领域,主要涉及图的邻接谱、Laplacian谱和Signless Laplacian(拟Laplacian)谱.图的谱确定问题于半个世纪前起源于化学.1956年Günthard和Primas在一篇把图谱理论与化学中Hiickels理论相联系的论文中提出了该问题.那时,人们认为所有的图都能由它的谱确定.但是,一年以后,Collatz和Sinogowotz找到了一对同谱图.现在,已找到了许多的同谱图.所谓一个图是谱确定的,是指没有别的不同构的图与之具有相同的谱.图的谱确定性理论在近年来得到了广泛的研究.图的谱确定性理论的研究,不仅丰富和发展了图论,而且在计算机科学、物理和化学中有着广泛的应用.
图的谱确定性理论研究的主要方法是用数学工具软件Maple,Matlab做大量的计算,结合GM(Godsil-Mckay)变化排除一些同谱图类,猜测可以谱确定的图,并由已有的谱性质证明其由谱确定.本文主要研究一些非正则图的邻接谱和Laplacian谱确定问题,得到了以下结论:
1.树图的谱确定问题.首先,给出了反例,说明两边具有相同顶点数的似双星树不能由其邻接谱确定.其次,证明了所有似双星树由其Laplacian谱确定.2.单圈图的谱确定问题.首先,证明了重合星图的中心点和圈图的一个点得到的章鱼图由Laplacian谱确定,并给出了章鱼图由邻接谱确定的猜想.其次,由矩阵变换,给出了一类邻接同谱单圈图和一类Laplacian同谱单圈图.最后,证明了一类由圈图Cp,路图Ps和星图K1,q组合得到的单圈图由Laplacian谱确定.
3.双圈图的谱确定问题.一般来说,邻接谱确定的证明要比Laplacian谱确定的证明困难得多.首先证明了最小双圈图,即沙漏图(Sandglass Graph)由其邻接谱及Laplacian谱确定.其次,由GM变换,给出了一些不能由邻接谱或Laplacian谱确定的双圈图类.最后,证明了由路图连接两个圈长相等的奇双圈图得到的图由其邻接谱确定.