DOI：10.16601/j.cnki.issn2096-7330.2024.01.001"文章編號：2096-7330（2024）01-0001-06

摘"要：對實數(shù)α∈"[0，1]，圖G的Aα-矩陣定義為Aα（G）=αD（G）+（1－α）A（G），其中D（G）和A（G）分別是G的度矩陣和鄰接矩陣.如果與G是Aα-同譜的圖都與G同構，則稱G是Aα-譜確定的.將星圖的中心與圈圖的一個頂點粘合所得到的圖稱為章魚圖，由s個三角形共同粘結在路上的一個端點所得到的圖稱為風輪圖.該文證明了對任意α∈（2/3，1），章魚圖和風輪圖都是Aα-譜確定的.

關鍵詞：Aα-譜；譜確定；同譜圖；章魚圖；風輪圖

中圖分類號：O157.5""""文獻標志碼：A

圖譜理論是代數(shù)圖論的一個重要研究方向，它主要研究與圖相關聯(lián)的矩陣（如鄰接矩陣、拉普拉斯矩陣、無符號拉普拉斯矩陣及距離矩陣等）的特征多項式、特征值以及特征向量等代數(shù)參數(shù)與圖的結構屬性（如團數(shù)、獨立數(shù)、匹配數(shù)以及色數(shù)等）間的關系. 描述哪些圖是由它們的譜確定的是圖譜理論中一個經典但困難的問題.1956年Günthard和Primas[1]將圖譜理論和化學分子軌道理論聯(lián)系在了一起.近年來證明了許多圖都是譜確定圖[2，3，4]，但圖的譜確定問題還遠沒有得到完全解決.

本文中的圖均為簡單無向的圖.設圖G=（V（G），E（G）），其中頂點集為V（G）={v1，v2，…，vn}，邊集為E（G）={e1，e2，…，en}.在G中，令di=d（vi）=dG（vi）為頂點vi的度且d1≥d2≥…≥dn，則G的度矩陣定義為D（G）=diag（d1，d2，…，dn）.圖G的拉普拉斯矩陣和無符號拉普拉斯矩陣分別定義為L（G）=D（G）－A（G）和Q（G）=D（G）+A（G）.

2017年Nikiforov[5]定義圖G的Aα-矩陣為Aα（G）=αD（G）+（1－α）A（G），

其中實數(shù)α∈[0，1].注意到A0（G）=A（G）且2A1/2（G）=Q（G），因此矩陣簇Aα（G）包含了A（G）和Q（G），它能將鄰接矩陣A（G）與無符號拉普拉斯矩陣Q（G）很好地統(tǒng)一起來，從而可以從一個全新的角度研究鄰接矩陣和無符號拉普拉斯矩陣.

由于Aα（G）的特征值都是實數(shù)，故可設Aα（G）的全部特征值為λ1（Aα（G））≥λ2（Aα（G））≥…≥λn（Aα（G）），其中最大特征值λ1（Aα（G））稱為G的Aα-譜半徑.矩陣Aα-（G）的特征值的全體稱為G的Aα-譜，記為Spec（Aα（G））.圖G與H稱為是Aα-同譜的，如果Spec（Aα（G））=Spec（Aα（H））；如果G的所有Aα-同譜圖都與G是同構的，則稱G是由Aα-譜確定的.對于d1≥d2≥…≥dn，圖G的度序列記為deg（G）=（d1，d2，…，dn）.設σ=（d1，d2，…，dn）和σ′=（d′1，d′2，…，d′n）是兩個非遞增的度序列，當且僅當∑n"i=1di=∑j"i=1d′i且∑j"i=1di≤∑j"i=1d′i時，其中1≤j≤n－1，稱σ被σ′優(yōu)超，記為σσ′.

記Cp和K1，q分別為p階圈圖和q+1階星圖.稱頂點數(shù)等于邊數(shù)的連通圖為單圈圖.現(xiàn)在已經知道Cp和K1，q分別由其A-譜、L-譜和Aα-譜確定[6，7].將K1，q的中心與Cp的一個頂點粘合所得到的圖稱為章魚圖，記為H（Cp，q），如圖1所示.由s個三角形共同粘結在路Pt+1的一個端點上所得到的圖稱為風輪圖，記為Gs，t.顯然Gs，0是n=2s+1階的友誼圖Fs.文獻[6]證明了友誼圖在α∈（1/2，1）時是Aα-譜確定的.本文證明了對任意α∈（2/3，1），圖H（Cp，q）和Gs，t都是Aα-譜確定的.

1"有關引理

引理1[7]"設圖G和G′的度序列分別為d1≥d2≥…≥dn和d′1≥d′2≥…≥d′n，如果Spec（Aα（G））=Spec（Aα（G′）），α∈［0，1］，則有：

（1） ｜V（G）｜=｜V（G′）｜.

（2） ｜E（G）｜=｜E（G′）｜.

（3） 如果G是r-正則圖，那么G′也是r-正則圖.

（4） ∑DD（X1≤i＜j≤ndidj=∑DD（X1≤i＜j≤nd′id′j.

（5） ∑ni=1d2i=∑ni=1d′i2.

引理2[8]"對于兩個非遞增序列x=（x1，x2，…xn）和y=（y1，y2，…yn），如果yx，那么=yJB）=22≤=x=22，等式成立當且僅當x=y.

引理3[9]"設G是n階圖，如果G沒有孤立頂點，則對任意α∈（1/2，1）都有λn（Aα（G））≥2α－1，等式成立當且僅當G有一個同構于K2的分支.

定義[10]"圖G的路v1v2…vk稱為內部的，如果d（v1）≥3，d（vk）≥3，且d（v2）=d（v3）=…=d（vk－1）=2.

引理4[10]"設G是連通圖，α∈［0，1），uv是G中一條內部路的邊，在G中剖分uv為uw和wv所得到的圖記作Guv，那么λ1（Aα（Guv））＜λ1（Aα（G））.

引理5[11]（交錯定理）"設N是n階實對稱方陣，其全部特征值為λ1≥λ2…≥λn，N的m階主子陣的特征值為λ′1≥λ′2…≥λ′m，則λi≥λ′i≥λn－m+i，i=1，2…，m.

引理6[12]"設G是n階單圈圖，則對任意α∈［0，1）都有λ1（Aα（G））≥λ1（Aα（Cn））=2，等式成立當且僅當GCn.

引理7[13]"設G是n階圖，e∈E（G），則對任意α∈（1/2，1）都有

λi（Aα（G））≥λi（Aα（G－e）），"i=1，2，…，n.

3引理8[14]"設圖G的度序列deg（G）=（d1，d2，…，dn）.對α∈（0，1），令Aα（G）的特征多項式為

fAα（G）（x）=∑nj=1cαj（G）n-j，

則有：

（i） cα0（G）=1."（ii） cα1（G）=-2αm."（iii） cα2=2α2m2-（1-α）2m-SX（12SX）α2∑nj=1d2r.

（iv） cα3（G）=-SX（13SX）（6（1-α）3tG-6α（1-α）2m2+

3α（1-α）2∑nj=1d2r+α3（4m3-3m∑nj=1d2r+∑nj=1d3r））.

式中m是G的邊數(shù)，tG為G中的三角形的個數(shù).

2"主要結果

引理9"對任意α∈（0，1），章魚圖H（Cp，q）的第二大Aα-特征值小于2.

證明"記G=H（Cp，q）.根據(jù)定義有

Aα（G）=（HL（10（q+2）α1－α0…01－α1－α1－α…1－α1－α001－αA11－α1－α1－αHL）），

其中A1=（HL（2A1100A22HL）），

A11=（HL（52α1－α0…01－α2α1－α000…1－α2α1－α0…01－α2αHL））（p－1）×（p－1），"A22=αE"（E為q階單位方陣）.

易知A1是Aα（G）的n－1階主子陣，于是由引理5有1.1mm

λ2（Aα（G））≤λ1（A1）=max{λ1（A11），λ1（A22）}=λ1（A11）.

另一方面，A11是Aα（Pp+1）的主子陣，又因為路的Aα-譜半徑小于2，故λ1（A11）≤λ1（Aα（Pp+1））＜2.所以λ2（Aα（G））＜2.

引理10"設圖G′與G∶=H（Cp，q）對任意α∈（2/3，1）都是Aα-同譜的，則有：

（1） G′的第二大頂點度d2≤3.

（2） G′中度不小于3的頂點的全體S所誘導的子圖G′[S]是一個團.

證明"令deg（G′）=（d1，d2，…，dn），d1≥d2…≥dn.若d2≥4，則因M′=（HL（2d1α1－α1－αd2αHL））是Aα（G′）的二階主子陣，直接計算可得λ2（M′）≥d2α+α－1≥5α－1gt;2，矛盾.若G′[S]不是一個團，則存在vi，vj∈S，且vi與vj不關聯(lián)，那么M=（HL（2diα00djαHL））是Aα（G′）的二階主子陣，根據(jù)引理5有λ2（Aα（G′））≥λ2（M）=min{diα，djα}≥3α＞2，這與λ2（Aα（G′））=λ2（Aα（G））＜2矛盾.

引理11"設圖G′與G∶=H（Cp，q）對任意α∈（2/3，1）都是Aα-同譜的，且p+q=n，則G′與G有相同的度序列.

證明"G的度序列為（q+2，2p－1，1q），其中指數(shù)代表圖中含有該度的頂點數(shù).令

σ=（a1，a2，…，an）=（q+2，2p－1，1q），"a1≥a2…≥an；

σ′=（d1，d2，…，dn）=deg（G′），"d1≥d2…≥dn.

根據(jù)引理3有dn≥1，再根據(jù)引理1的（2）和（5）有

∑ni=1di=2n=2（p+q），JY，2（2.1）

∑ni=1d2i=∑ni=1a2i=q2+5q+4p.JY，2（2.2）

我們斷言d1≤q+2.

當p=3時該斷言顯然成立.

當p≥4時，根據(jù)引理10，G′的度數(shù)不小于3的頂點最多4個，故由上述關系式，d2，d3和d4的取值只有四種情況：（d2，d3，d4）=（3，3，3），（3，3，2），（3，2，2）或（2，2，2）.若d1≥q+3，則因dn≥1，故由（2.1）可知，G′的度序列可能為：（i） （q+a，33，2p－a－5，1q+a+1），（ii） （q+a，32，2p－a－3，1q+a），（iii） （q+a，3，2p－a－1，1q+a－1）或（iv） （q+a，2p－a+1，1q+a-2），其中a≥3為整數(shù).

在情況（i）時有

∑ni=1d2i=q2+（2a+1）q+4p+（a－3）a+8gt;q2+5q+4p，

與（2.2）矛盾.可類似地證明情況（ii）、（iii）和（iv）也不可能.

當d1=q+2時，由（2.1）得∑ni=1di=2（p+q）=∑ni=1ai.接下來證∑si=1di≥∑si=1ai，s＜n.當s=1時有d1=q+2≥a1，假設∑s-1i=1di≥∑s-1i=1ai成立，討論以下兩種情況：

當ds=1時有∑ni=s+1di≤∑ni=s+1ai，則∑si=1di≥∑si=1ai.

當ds≥2時有∑si=1di≥2s+q≥∑si=1ai，這意味著σσ′，因為∑ni=1d2i=∑ni=1a2i，即=σ=22==σ′=22，再根據(jù)引理2有σ′=σ，故當d1=q+2，有deg（G′）=deg（G）.

當d1≤q+1時，根據(jù)引理3有dn≥1，結合引理10，得

deg（G′）=σ′=（d1，d2，…，dn）=（d1，3s，2t，1k）.

由兩個圖同階和關系式（2.1）、（2.2），有

{s+t+k=p+q－1，d1+3s+2t+k=2（p+q），d21+9s+4t+k=q2+5q+4p.

從而有d1+s－k=2，d21+3s－k－2d1=q2+q.整理得d21－3d1+2s=（q+2）（q－1）.因為d1≤q+1，由引理10得1≤s≤3，故有d21－3d1+2s≥2s≥2，即（q+2）（q－1）≥2，q≥2.又

（q+2）（q－1）=d21－3d1+2s=d1（d1－3）+2s≤（q+1）（q－2）+2s，

故q≤s，即q≤3，所以q=2或3.

上述論證表明，當q≥4時必有d1=q+2，從而deg（G）=deg（G′）.

接下來討論q=2，3時（如圖2和圖3）的情形.

當q=2時deg（G）=（4，2n－3，12）.記deg（G′）=（d1，d2，…dn），注意d1≤4，若d1=4，則由上述證明得deg（G）=deg（G′）.當d1≤3時，令deg（G′）=（3k，2l，1h），則由引理1得

{k+l+h=n，3k+2l+h=2n，9k+4l+h=4n+6，

解得k=h=3，l=n－6，故deg（G′）=（33，2n－6，13）.結合引理10可知，

存在頂點集XV（G′），使得G′[X]同構于含有6個頂點的太陽圖S3（如圖4），于是tG′=1.又因為tG=0，m（G）=m（G′），且∑ni=1d2i（G′）=∑ni=1d2i（G），根據(jù)引理8的（iv）有cα3（G′）≠cα3（G），從而G′與G的Aα-特征多項式不同，矛盾.故此時有deg（G′）≠（33，2n－6，13） ，即deg（G′）=deg（G）=（4，2n－3，12）.

當q=3時deg（G）=（5，2n－4，13）.記deg（G′）=（d1，d2，…dn），注意d1≤5.當d1=5時顯然有deg（G）=deg（G′）.當d1≤4時，令deg（G′）=（4，3k′，2l′，1h′），則有

{1+k′+l′+h′=n，4+3k′+2l′+h′=2n，16+9k′+4l′+h′=4n+12，

解得k′=3，h′=5，l′=n－9，從而deg（G′）=（4，33，2n－9，15）.根據(jù)引理10，存在頂點集YV（G′）使得G′[Y]K14，其中K14是在K4的一個頂點上添加一條懸掛邊所構成的圖（稱為菠蘿圖，如圖5）.于是tG′=4.又因為tG=0，m（G）=m（G′），且∑ni=1d2i（G′）=∑ni=1d2i（G），由引理8的（iv）得cα3（G′）≠cα3（G），故G′與G的Aα-特征多項式不同，矛盾.所以當q=3時有deg（G′）≠（4，33，2n－9，15），從而deg（G）=deg（G′）=（5，2n－4，13）.引理11證畢.

定理1"對任意α∈（2/3，1），章魚圖H（Cp，q）都是Aα-譜確定的，其中p+q=n.1.25mm

證明"設G′與G=H（Cp，q）是Aα-同譜的，則由引理10可知deg（G）=deg（G′）=（q+2，2p－1，1q）.考慮所有被度序列（q+2，2p－1，1q）所確定的圖：

（1） G′G.

（2） G′H∪S，其中H是將q條長度大于等于1的路粘貼在Ck的同一個頂點上得到的圖，k＜p，S是t個圈的并（t為自然數(shù)）.

對于情況（2），當t=0時有G′H，則G′的內部路比G的內部路短，于是由引理4和引理7得λ1（Aα（G′））＞λ1（Aα（G）），矛盾.而當t≥1時，由引理6可得λ1（Aα（H））≥2，λ1（Aα（S））=2，故λ2（Aα（G′））=2，這與在引理9的證明中得到的λ2（Aα（G））＜2矛盾.

所以必有情況（1）成立.

定理2"對任意2/3＜α＜1，風輪圖Gs.t都是Aα-譜確定的.

證明"令G=Gs.t（如圖6），v是G中度為2s+1的頂點，設M為在Aα（G）中刪去頂點v對應的行和列所得的矩陣，則M只有兩種塊型：

一種是s個M1=（HL（22α1－α1－α2αHL）），另一種是一個M2=（HL（52α1－α0…01－α2α1－α000…1－α2α1－α0…01－ααHL））t×t，

λ1（M1）=α+1，M2是道路Pt+1的主子陣，λ1（M2）＜2，故λ2（Aα（G））＜2.

設G′與G是Aα-同譜的，令

deg（G）=（2s+1，22s+t－1，1）=π，"deg（G′）=（d1，d2，…dn）=π′.

當d1≥2s+1時易知ππ′，又‖π‖22=‖π′‖22，故由引理2可知π=π′.

當d1≤2s時，注意到λ2（G）＜2，由類似于引理10的證明可得，在G′中度數(shù)不小于3的頂點所構成的集合誘導的子圖是一個團且d2≤3.根據(jù)引理3知dn≥1，故有

deg（G′）=（d1，d2，…，dn）=（d1，3r，2l，1k）.

結合引理1，得

{r+l+k=2s+t，d1+3r+2l+k=6s+2t，d21+9r+4l+k=4s2+12s+4t－2.

+1從而有d1+r－k=2s，d21+3r－k－2d1=4s2－2.整理得d21－3d1+2r=（2s+1）（2s－2）.因d1≤2s，且G′中由度數(shù)不小于3的頂點所構成的頂點集所誘導的子圖是一個團，所以1≤r≤3.于是有d21－3d1+2r≥2r≥2，即（2s+1）（2s－2）≥2，因為s是整數(shù)，所以s≥2.又（2s+1）（2s－2）=d21－3d1+2r=d1（d1－3）+2r≤2s（2s－3）+2r，故s≤r/2+1/2，即s≤2，所以s=2.當s=2時，G=G2，n－2（如圖7），deg（G）=（5，2n－2，1），因為d1≤5，d2≤3，1≤r≤3，故deg（G′）=（5，2n－2，1）或（4，33，2n－7，13）.

若deg（G′）=（4，33，2n－7，13），則存在頂點集XV（G）使得G′[X]K14.于是tG′=4.又因為tG=2，m（G）=m（G′），且∑ni=1d2i（G′）=∑ni=1d2i（G），根據(jù)引理8的（iv）有cα3（G′）≠cα3（G），故G′與G的Aα-特征多項式不同，矛盾.所以當s=2時有deg（G′）=deg（G）=（5，2n－2，1）=（2s+1，22s+t－1，1）.

考慮所有被度序列（2s+1，22s+t－1，1）所確定的圖：

（1） G′G.

（2） G′Gs，t′∪S，其中t′＜t，S是若干個圈的不交并.

（3） G′H，其中H是s個Ck（k≥3）共同粘結在路Pt′+1的一個端點所構成的圖，t′＜t.

（4） G′H′∪S，其中H′是s個Ck（k≥3）共同粘結在路Pm+1的一個端點所構成的圖，m＜t′，S是若干個圈的不交并.

對于情況（2），有λ2（Aα（G′））=2，因為G′與G是Aα-同譜的，這與λ2（Aα（G））＜2矛盾.情況（4）同理.對于情況（3），根據(jù)引理4和引理7有λ1（Aα（G′））＜λ1（Aα（G）），矛盾.

定理得證.

3"結束語

本文研究了章魚圖和風輪圖在2/3＜α＜1時的Aα-譜確定問題.我們先證明了章魚圖的第二大Aα-特征值小于2；借助兩個圖在Aα-同譜情況下度和以及度平方和相等的基本工具，推導出與章魚圖Aα-同譜的圖度序列都是一致的；再考慮該度序列所確定的圖，排除不同構的情況，從而證明了章魚圖是Aα-譜確定的.類似地證明了風輪圖也是Aα-譜確定的.而對于α∈（0，SX（23SX）］，由于不能確定這兩類圖的Aα-矩陣的第二大特征值的上界，故無法利用第二大Aα-特征值來輔助確定這兩類圖的Aα-同譜圖的度序列，所以目前還沒有辦法確定α∈（0，SX（23SX）］時，這兩類圖的Aα-譜確定性.后續(xù)我們將嘗試用其他不同的方法來確定當α∈（0，1）時，這兩類圖是否也是Aα-譜確定的.

參考文獻：

[1]"Günthaed H H， Prtmas H. Zusammenhang von graphentheorie und MO-theorie von molekeln mit systemen konjugierter bindungen[J]. Helvetica Chimica Acta，1956，39（6）：1645-1653.

[2]"Chen Y Y， Li D， Meng J X. On the second largest Aα-eigenvalues of graphs[J]. Linear Algebra and Its Applications， 2019，580：343-358.

[3]"Zhang Y， Liu X G， Yong X R. Which wheel graphs are determined by their Laplacian spectra？[J]. Computers Mathematics with Applications，2009，58（10）：1887-1890.

[4]"Das K C， Liu M H. Kite graphs determined by their spectra[J]. Applied Mathematics and Computation， 2017，297：74-78.

[5]"Nikiforov V. Merging the A-and Q-spectral theories[J]. Applicable Analysis. Discrete Mathematics， 2017，11（1）：81-107.

[6]"Lin H Q， Zhang L W， Xue J. Majorization， degree sequence and Aα-spectral characterization of graphs[J]. Discrete Mathematics，2020，343（12）：112-132.

[7]"Lin H Q， Liu X G， Xue J. Graphs determined by their Aα-spectra[J]. Discrete Mathematics， 2019，342（2）：441-450.

[8]"Lin H Q， Ning B， Wu B. Eigenvalues and triangles in graphs[J]. Combinatorics， Probability and Computing， 2021，30（2）：258-270.

[9]"Lin H Q， Xue J， Shu J L. On the Aα-spectra of graphs[J]. Linear Algebra and Its Applications， 2018，556：210-219.

[10]Li D， Chen Y Y， Meg J X. The Aα-spectral radius of trees and unicyclic graphs with given degree sequence [J]. Applied "Mathematics and Computation， 2019，363：124622.

[11]Dam E R V， Haemers W H. Which graphs are determined by their spectrum？[J]. Linear Algebra and Its Applications， 2003，373：241-272.

[12]He H， Ye M L， Xu H. On the Aα-spectrum of a unicyclic graph[J]. Journal of Combinatorial Optimization， 2023，45：38.

[13]Lin H Q， Xue J， Shu J L. On the Aα-spectra of graphs[J]. Linear Algebra and Its Applications， 2018，556：210-219.

[14]Liu X G， Liu S Y. On the Aα-characteristic polynomial of a graph[J]. Linear Algebra and Its Applications，2018，546（1）：274-288.

[責任編輯：彭喻振]

收稿日期：2023-07-19

*基金項目：國家自然科學基金項目（12171089）

第一作者簡介：劉劍萍（1978—），女，福建莆田人，副教授，博士，研究方向：圖論及其應用。