论文部分内容阅读
谱图理论主要研究图的(Laplace谱或邻接)特征值与图的结构联系．本文所研究的广义Bethe树来源于理论计算机科学中的二叉树以及Bethe树．这两类图在计算机科学中的数据搜索等发挥着重要的作用．广义Bethe树视为上述两类图的推广，在未来计算机科学中有着潜在的应用价值。 2005年，Rojo和Soto引入广义Bethe树Bk，并对其Laplace谱和邻接谱展开讨论，用蕴含度信息的三对角矩阵的谱来描述广义Bethe树的谱．而度信息是广义Bethe树的关键信息．因此Rojo和Soto建立了该类图的结构与谱的联系．2006年，Rojo把原来广义Bethe树推广到一种新的图类B(2)k，即是由BK的两个拷贝图在它们根节点之间连一条边而获得．2007年，Rojo讨论了另一类图的B(r)k它是由由一个圈Tr和Bk的r个拷贝图通过粘贴Tr的点和Bk的根节点而得．Rojo对上述两类图获得了以度表示的谱． 受Rojo等人研究工作的启发，我们的工作分为两个阶段： (1)引入图Bk.Kr并讨论它的谱，其中Bk.Kr是由一个完全图Kr和Bk的r个拷贝图通过粘贴Kr的点和Bk的根节点而得； (2)考虑到K2(一条边)，Tr，Kr都是可迁图，讨论更一般的图Bk.Jr,其中Bk.Jr是由一个可迁图Jr和Bk的r个拷贝图通过粘贴Kr的点和Bk的根节点而得．所以，Rojo等人所讨论的图都是本类图的特殊情形．故我们的工作推广了已有的相关工作． 本文讨论了所引入的两类图的Laplace谱和邻接谱，用蕴含Bk的度及Kr(和Jr)的谱的三对角矩阵的谱，来表示Bk.Kr(和Bk.Jr)的邻接谱和Laplace谱，并对一些极端特征值重数进行讨论，特别地，对一些极端特征向量(如邻接矩阵的Perron向量，Laplace矩阵的Fiedler向量)的组合结构性质进行了探讨，获得一些有意义的结论． 本文的结构如下：第一章介绍谱图理论的研究背景，本文所用的概念和记号，研究问题的进展及本文的主要结论．第二章引入基于广义Bethe树的一个新的图类，即Bk.Kr,获得其邻接谱和Laplace谱的相关性质．第三章引入基于广义Bethe树的更一般的图类，即Bk.Jr，它推广了目前基于广义Bethe树的所有图类．我们从更一般的研究研究该类图，获得其邻接谱和Laplace谱的相关性质．