具SR性質(zhì)的基本雙圈圖

周后卿，張于娟

(1.湖南邵陽學(xué)院數(shù)學(xué)系，中國 邵陽 422000；2.湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，中國 長沙 410081)

設(shè)G為n階簡單圖，其頂點(diǎn)集為V(G)={v1,v2,…,vn}，G的鄰接矩陣記為A(G)，由于A(G)是實(shí)對(duì)稱矩陣，則所有的特征值也是實(shí)數(shù)，A(G)的特征值也稱為G的譜.若A(G)是奇異的(或非奇異的)，則圖G稱為奇異的(或非奇異的).定義與記號(hào)見參考文獻(xiàn)[1].

若圖G存在一生成森林使得每一分支是僅2個(gè)點(diǎn)的路，則稱G具有完美匹配.一般地，1個(gè)圖可能存在不止1個(gè)完美匹配，而若樹存在完美匹配，則完美匹配是唯一的，且此時(shí)樹是非奇異的.容易看出，具唯一完美匹配的圖是非奇異的.單圈圖和雙圈圖的結(jié)構(gòu)決定了鄰接矩陣的奇異性，文[2]刻畫了單圈圖的鄰接矩陣的奇異性與非奇異性分類.文[3～5]研究了雙圈圖的鄰接矩陣的奇異性與非奇異性的分類.

本文作者考慮的是基本雙圈圖，即不含懸掛點(diǎn)的連通雙圈圖，它共有3種不同的類型(見圖1)：

圖1 基本雙圈圖

圖2 圖H

對(duì)任一圖G，若S為G的一個(gè)點(diǎn)集或邊集，則G-S表示由G刪去所有S的元素得到的圖.G的Sach子圖L是其連通分支為邊和圈的子圖，當(dāng)L的頂點(diǎn)集與G相同時(shí)，稱L為G的生成Sach子圖.G的k-匹配是指k條不相交的邊的并，若e1,e2,…,ek為k-匹配M中的邊，記作M={e1,e2,…,ek}.若2k為G的頂點(diǎn)數(shù)，則G的k-匹配為G的一個(gè)完美匹配，記m0(G)為G的完美匹配數(shù).

1 主要結(jié)果和證明

本節(jié)利用圖具有SR性質(zhì)的必要條件出發(fā)來研究基本雙圈圖的SR性質(zhì)，得出只有圖H具有SR性質(zhì)，而其他圖都不具有SR性質(zhì).

引理1[10]設(shè)G為n階具有SR性質(zhì)的圖，鄰接矩陣A(G)的特征多項(xiàng)式為P(G;x)=a0xn+a1xn-1+…+an,則|ai(G)|=|an-i(G)|,其中i=0,1,…,n.

從上可知，若某圖G的特征多項(xiàng)式P(G;x)中有|ai(G)|≠|(zhì)an-i(G)|,則G不具有SR性質(zhì).

引理2設(shè)G為n階基本雙圈圖且G=B(p,q)(p≥q≥3),兩基圈分別為Cp,Cq,則G不具SR性質(zhì).

證用反證法，假設(shè)G具有SR性質(zhì)，則|an(G)|=1,由于

an(G)=±(m0(G)±2m0(G-Cp)±2m0(G-Cq))，

(1)

1)若G有完美匹配，則n為偶數(shù)，此時(shí)m0(G)=2,由式(1)得an(G)=0(mod 2)與|an(G)|=1矛盾，所以此類圖不具有SR性質(zhì)；

2)若G沒有完美匹配，此時(shí)m0(G)=0,由式(1)得an(G)=0(mod 2)與|an(G)|=1矛盾，所以此類圖不具有SR性質(zhì).

綜上，基本雙圈圖G=B(p,q)(p≥q≥3)不具有SR性質(zhì).

引理3設(shè)G為n階基本雙圈圖且G=B(p,l,q)，p≥q≥3,l≥2,兩基圈分別為Cp,Cq,則G不具有SR性質(zhì).

證由于n階基本雙圈圖G=B(p,l,q)中，

an(G)=±(m0(G))±2m0(G-Cp)±2m0(G-Cq)±4m0(G-Cp-Cq),

(2)

且p+q+l-2=n,假設(shè)G具有SR性質(zhì)，必有|an(G)|=1.

1)若G有完美匹配，則n為偶數(shù)，對(duì)l分情況討論：

(1)當(dāng)l=1(mod 2),則p+q=1(mod 2),此時(shí)m0(G)=2,由式(2)得an(G)=0(mod 2)與|an(G)|=1矛盾，所以G不具SR性質(zhì).

(2)當(dāng)l=0(mod 2),只能p=0(mod 2),q=0(mod 2),或p=1(mod 2),q=1(mod 2):①p=0(mod 2),q=0(mod 2),此時(shí)m0(G)=4代入式(2)得an(G)=0(mod 2)與|an(G)|=1矛盾，則G不具SR性質(zhì)；②p=1(mod 2),q=1(mod 2),此時(shí)m0(G)=1,m0(G-Cp)=0,m0(G-Cq)=0,m0(G-Cp-Cq)=1,代入式(2)得an(G)=±3或±5，矛盾，則G不具SR性質(zhì).

2)若G沒有完美匹配，則m0(G)=0,由式(2)得an(G)=0(mod 2)，與|an(G)|=1矛盾，則G不具SR性質(zhì).

綜上，基本雙圈圖G=B(p,l,q)不具SR性質(zhì).

引理4設(shè)G=B(Pp+2,Pl,Pq+2)(l≥2,p≥q≥1)為n階基本雙圈圖且|an(G)|=1,則p,q,l必為下列6種情形之一：(1)l=0(mod 4),p=0(mod 4),q=0(mod 4);(2)l=0(mod 4),p=0(mod 4),q=2(mod 4);(3)l=0(mod 4),p=2(mod 4),q=0(mod 4);(4)l=2(mod 4);p=0(mod 4),q=2(mod 4);(5)l=2(mod 4),p=2(mod 4),q=0(mod 4);(6)l=2(mod 4),p=2(mod 4),q=2(mod 4).

證設(shè)n階基本雙圈圖G=B(Pp+2,Pl,Pq+2)滿足|an(G)|=1.由

an(G)=±(m0(G)±2m0(G-Γ1)±2m0(G-Γ2)±2m0(G-Γ))

(3)

知m0(G)≠0.故G有完美匹配，從而n為偶數(shù).對(duì)p,q,l的取值分類討論：

1)l=1(mod 2)時(shí)，必有p+q=1(mod 2),此時(shí),m0(G)=2,代入式(3)得an=0(mod 2);

2)l=0(mod 2)時(shí)，必有p+q=0(mod 2):

(1)當(dāng)p=1(mod 2),q=1(mod 2)時(shí)，m0(G)=2,代入式(3)得an=0(mod 2);

(2)當(dāng)p=0(mod 2),q=0(mod 2)時(shí)，m0(G)=3,m0(G-Γ1)=1,m0(G-Γ2)=1,m0(G-Γ)=1,代入式(3)得an=±(3±2±2±2),分下列情況：

情形①:l=0(mod 4),p=2(mod 4),q=2(mod 4),an=+(3+2+2+2)=9;

情形②:l=2(mod 4),p=0(mod 4),q=0(mod 4),an=-(3+2+2+2)=-9;

情形③:l=0(mod 4),p=0(mod 4),q=0(mod 4),an=+(3-2-2+2)=1;

情形④:l=0(mod 4),p=0(mod 4),q=2(mod 4),an=-(3-2+2-2)=-1;

情形⑤:l=0(mod 4),p=2(mod 4),q=0(mod 4),an=-(3+2-2-2)=-1;

情形⑥:l=2(mod 4),p=0(mod 4),q=2(mod 4),an=+(3-2+2-2)=1;

情形⑦:l=2(mod 4),p=0(mod 4),q=2(mod 4),an=+(3+2-2-2)=1;

情形⑧:l=2(mod 4),p=2(mod 4),q=2(mod 4),an=-(3-2-2+2)=-1.

綜上，得證.

引理5設(shè)G為n階基本雙圈圖且G=B(Pp+2,Pl,Pq+2),l=0(mod 2),p=0(mod 2),q=0(mod 2)，則

(4)

若為3)，則是去掉路Pp+2上的兩點(diǎn)(不包括端點(diǎn))后有生成Sach子圖可能含圈Γ2，此時(shí)

(5)

若為4)，則是去掉公共路Pl上的兩點(diǎn)(包括端點(diǎn))后有生成Sach子圖可能含圈Γ，此時(shí)

(6)

整理后即得結(jié)論.

定理1設(shè)G為n階基本雙圈圖且G=B(Pp+2,Pl,Pq+2)，則只有當(dāng)n=6,p=q=l=2時(shí)，此時(shí)圖G=B(P4，P2，P4)有SR性質(zhì)，而其他圖都不具SR性質(zhì).

證由引理4知|an(G)|=1的情形，而an-1(G)=0,現(xiàn)考慮an-2(G),由引理1知，G若不滿足|an-2(G)|=|a2(G)|,則G一定不具SR性質(zhì).由于p+q+l=n,下面分情況討論：

(1)l=0(mod 4),p=0(mod 4),q=0(mod 4),不妨設(shè)l=2k0,p=2k1,q=2k2(k0,k1,k2均為偶數(shù))，由引理5知

|a2(G)|=n+1=p+q+l+1=2k1+2k2+2k0+1，

因?yàn)閗0≥2,k1≥2,k2≥2,則|an-2(G)|-|a2(G)|>0,與圖G具有SR性質(zhì)的必要條件|an-2(G)|=|a2(G)|矛盾，所以此類圖不具SR性質(zhì).

(2)l=0(mod 4),p=0(mod 4),q=2(mod 4);(3)l=0(mod 4),p=2(mod 4),q=0(mod 4);(4)l=2(mod 4),p=0(mod 4)，q=2(mod 4);(5)l=2(mod 4),p=2(mod 4),q=0(mod 4),利用(1)的方法，可得|an-2(G)|-|a2(G)|>0.

(6)l=2(mod 4),p=2(mod 4),q=2(mod 4),不妨設(shè)l=2k0,p=2k1,q=2k2(k1,k0,k2均為奇數(shù))，由引理3知

|a2(G)|=n+1=p+q+l+1=2k1+2k2+2k0+1,

因?yàn)閗0≥1,k1≥1,k2≥1,則|an-2(G)|-|a2(G)|≥0,等號(hào)成立當(dāng)且僅當(dāng)k1=k2=k0=1,即p=q=l=2.從而G為圖H.

參考文獻(xiàn)：

[1] HARARY F. Graph theory[M]. Addition-Wesley, 1969.

[2] 扈生彪.單圈圖的鄰接矩陣的分類及其最大行列式[J].數(shù)學(xué)研究，2003，36(1)：102-104.

[3] 何梅芝.恰有一公共點(diǎn)的雙圈圖的鄰接矩陣的奇異性[J].南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，20(1)：40-43.

[4] 兀靜.n階雙圈圖的鄰接譜矩陣[J].海南師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2006，19(4)：289-300.

[5] 謝小花，陳寶興，陳 宇.有交雙圈圖鄰接矩陣的奇異性[J].漳州師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2007，2：7-10.

[6] BARIK S, NEUMANN M, PATI S. On nonsingular trees and a reciprocal eigenvalue property[J].Linear and Multilinear Algebra, 2006,54: 453-465.

[7] FRUCHT R, HARARY F. On the corona of two graphs[J].Aequationes Math,1970,4:322-325.

[8] BARIK S, NATH M, PATI S,etal. Unicyclic graphs with the strong reciprocal eigenvalue property[J]. Electronic Journal of Linear Algebra, 2008,17:139-153.

[9] CVETKOVIC D M, DOOB M, SACHS H. Spectra of graphs[M]. New York:Academic Press,1979.

[10] BARIK S, PATI S, SARMA B K.The spectrum of the corona of two graphs[J]. SIAM J Discrete Math, 2007,21:47-56.