哈密爾頓圖的譜充分條件

許秋晨，葉淼林

（安慶師范大學(xué) 數(shù)理學(xué)院，安徽 安慶 246133）

設(shè)G=G(V,E)為n階簡單連通圖，其頂點(diǎn)集V=V(G)={v1,v2,v3,…,vn}，邊集E=E(G)為V的二元重集構(gòu)成的集合，稱E中元素{u,v}( u ≠v)為G的邊，邊{u,v}簡記為uv。頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊數(shù)，G的最小度記作δ。圖G的鄰接矩陣為A(G)=[aij]n×n，當(dāng)vi,vj相鄰時(shí)，aij=1，否則aij=0，i,j=1,2,3,…,n，稱A(G)的最大特征值為圖G的譜半徑，用ρ(G)來表示，簡記為ρ。設(shè)D(G)=diag(d(v1),d(v2),d(v3),…,d(vn))是圖G的度對角矩陣，定義圖G的無符號拉普拉斯矩陣Q(G)=D(G)+A(G)，Q(G)的最大特征值被稱為圖G的無符號拉普拉斯譜半徑，記作q(G)，簡記為q。

1 預(yù)備知識

引理1[1]設(shè)G是階數(shù)大于4 的圖，且度序列為(d1,d2,d3,…,dn)，如果不存在一個(gè)整數(shù)使得dk≤k，dn-k≤n-k-1，則G是哈密爾頓圖。

2 主要結(jié)果

圖1 ～

表1 圖的譜半徑和無符號拉普拉斯譜半徑

3 結(jié)論

圖的哈密爾頓問題一直是圖論中的經(jīng)典問題，但是迄今為止，該問題依然是NP-完全問題，還沒有被完美地解決，仍有許多問題值得研究。目前，已有許多學(xué)者對圖的哈密爾頓性進(jìn)行了研究，也得出了一些結(jié)論，如周倩楠等[8]借助邊的大小給出了圖是哈密爾頓的充分條件。受文獻(xiàn)[8]的啟發(fā)，本文主要改進(jìn)圖的邊數(shù)條件，提出了哈密爾頓圖的邊充分條件，并在此基礎(chǔ)上給出了哈密爾頓圖的譜充分條件，豐富了圖的性質(zhì)研究。