论文部分内容阅读
图谱理论主要是使用代数方法来研究图的谱。“Which graphs are determined by their spectrums”在图谱理论中是一个很著名的问题,但是这个问题很难回答。到目前为止,这个问题还远没有解决。通常,如果任何一个图与图G同谱,那么这个图只有与图G同构,图G才被称为是由其谱决定的,我们把这样的图简称为DS(determined by the spectrum)图。一般情形下,无论你是选择邻接矩阵,拉普拉斯矩阵,或者其他形式的矩阵来描述图,除了一些具有特殊结构的图外,大部分图都是不能和自己的谱一一对应的。
由于这个问题非常困难,我们主要研究一些结构比较简单的图,比如图Dn和Qn,图Dn是由图C3、Pn的不交并C3UPn,通过一条边连结C3中的一度点和Pn中的一度点得到的,其中C3表示包含3个点的圈,Pn表示包含n个点的路径;而图Qn是由图Cn、P1的不交并CnUP1,通过一条边连结Cn中的一度点和P1得到的,其中Cn表示包含n个点的圈,P1表示包含1个点的路径,即孤立点。在这篇论文中,我们将证明图Dn和Qn是由其邻接矩阵的谱唯一决定的。进一步,我们定义了图En和Qn.2,分别与图Dn和Qn相似。通过对它们的谱半径的估计,我们同样证明了图En和Qn.2也是由其邻接矩阵的谱唯一决定的。