论文部分内容阅读
图论知识在物理、化学、计算机科学等几乎所有的学科领域的广泛应用,一方面极大地促进了图论的发展,同时一系列极富挑战性的新问题也应运而生。基于图参数的极值问题是图论科学中的极富挑战性的研究热点问题之一。
图的能量即其对应邻接矩阵的特征值绝对值的和;图的Hosoya指标为图中所有匹配数的和;图的Merrifeld-Simmons指标为图中所有独立集数的和:图的谱半径是相应图矩阵的最大特征值。本文通过对不同图类结构的分析,具体研究了基于图的能量、Hosoya指标和Merrifield-Simmons指标、Laplacian谱半径、Signless Laplacian谱半径等几个图参数的极值问题。本文的主要工作如下:
1、通过对三圈图结构特征的深入分析,利用数学归纳法巧妙地部分解决了由Caporossi等人提出的一个关于图能量的猜想对不含长p、q满足p+q≡2 mod(4)的奇圈的三圈图的正确性,并刻画了能量第一、第二小的三罔图的结构。同时,利用该方法进一步研究了一类单圈图,刻画了能量第四小、第五小和第六小的单圈图的结构。
2、集中研究了双圈图、三圈图、θ图、给定直径的单圈图的Hosoya指标和Merrifield-Simmons指标的极值图问题,并完整的刻画了相应的极值图。同时,分析比较了这两类指标的对称性问题。
3、具体研究了给定围长的三圈图的Laplacian谱半径,给定围长的双圈图Signless Laplacian谱半径,以及给定匹配数的图类的距离倒数矩阵的谱半径,并给出了相应谱半径的上界,同时刻画了相应的极值图。