图谱确定性研究.pdf

博}：学位论丈 摘要 图的谱确定性理论是图论中的一个新兴领域，主要涉及图的邻接谱、Laplacian 谱和Signless 中提出了该问题．那时，人们认为所有的图都能由它的谱确定．但是，一年以后， 图是谱确定的，是指没有别的不同构的图与之具有相同的谱． 图的谱确定性理论在近年来得到了广泛的研究．图的谱确定性理论的研究，不 仅丰富和发展了图论，而且在计算机科学、物理和化学中有着广泛的应用． 图的谱确定性理论研究的主要方法是用数学工具软件Maple，Matlab做大量的 已有的谱性质证明其由谱确定． 本文主要研究一些非正则图的邻接谱和Laplacian谱确定问题，得到了以下结 论： 1．树图的谱确定问题．首先，给出了反例，说明两边具有相同顶点数的似双星 树不能由其邻接谱确定．其次，证明了所有似双星树由其Laplacian谱确定． 2．单圈图的谱确定问题．首先，证明了重合星图的中心点和圈图的一个点得到 的章鱼图hqLaplacian谱确定，并给出了章鱼图由邻接谱确定的猜想．其次，由矩阵变 换，给出了一类邻接同谱单圈图和一类Laplacian同谱单圈图．最后，证明了一类由 圈图q，路图只和星图K1，。组合得到的单圈图Laplacian谱确定． Graph)由其邻接谱 证明困难得多．首先证明了最小双圈图，即沙漏图(Sandglass 定的双圈图类．最后，证明了由路图连接两个圈长相等的奇双圈图得到的图由其邻 接谱确定． 关键词：图谱理论，同谱图，邻接谱，Laplacian谱，特征值，特征多项式，谱半径，似 双星树，线图，单圈图，双圈图，沙漏图． 图的谱确定性研究 Abstract The determinationof isanewfieldin spectral theorygraph graphtheory, whichis concernedwiththe mainly adjacencyspectrum，theLaplacianspectrum andthe aredetermined signless graplls Laplacianspectrum．Thequestion“which their backforhalf a from by century，and chemistry．In spectra?’’goes originates andPrimasraisedthe ina thatrelatesthe 1956，Gfinthard questionpaper theory of toHiickel’S from thattimeitwasbelieved graphspectra theorychemistry．At that isdeterminedits untilone laterCollatzand every graph by spectrum year a of Sinogowitzpresentedpaircospectralgraphs．Now，manyc