T(2,2,n)∪(Ci)的匹配等價圖類

詹福琴, 喬友付

(河池學院數學系,廣西宜州 546300)

詹福琴, 喬友付

(河池學院數學系,廣西宜州 546300)

利用圖的匹配多項式及其最大實數根的性質完整刻畫了T(2,2,n)∪(Ci)(n≥3,A是大于等于3的整數組成的可重集)的匹配等價圖類.

匹配多項式;匹配等價;匹配唯一;最大實數根

1 引 言

本文僅考慮有限,無向簡單圖.設G是有n個頂點的圖,V(G),E(G)分別表示G的頂點集和邊集. G的一個匹配是指G的一個生成子圖,它的每個分支或是孤立點或是孤立邊.t-匹配是指其中有t條邊的匹配.文[1]定義圖G的匹配多項式為

其中at(G)是G的t-匹配的數目.兩個圖G和H,若有μ(G,x)=μ(H,x),則稱G和H匹配等價,記為G～H.若與圖G匹配等價的任何圖H,均有G?H,則稱圖G是匹配唯一的.Φ(G,x) =det(λI-A(G))表示圖G的特征多項式.其中A(G)表示圖G的鄰接矩陣,λ1(G)表示Φ(G,x)的最大特征根.M(G,x)表示圖G匹配多項式μ(G,x)的最大實數根.

Pn,Cn分別表示有n個點的路和圈;Q(s,t)(s≥2,t≥1)表示圈Cs+1上的一點與路Pt+1的一個端點粘接后得到的圖;T(a,b,c)表示從一點引出三條長分別為a,b,c(a≤b≤c)的路得到的圖; T(a,b,n,c,d)表示從路Pn+1的兩個1度點分別引出長為a,b和c,d的路得到的圖,特別地,當a=b=c=d=1時,該圖表示為Un(n≥6);ˉG表示圖G的補圖.

為方便,用μ(G)表示μ(G,x);M(G)表示M(G,x).文中其他未特別說明的概念和術語均參見[1-2].

2 基本定義和引理

引理1[1]設圖G有k個連通分支：G1,G2,…,Gk,則

引理2[1]設e=uv是圖G的一條邊,則μ(G,x)=μ(G-e,x)-μ(G-{u,v},x),這里G-e, G-{u,v}分別表示從G中刪去邊e,頂點u,v后得到的圖.

引理3[1]設u∈V(G),e∈E(G),且G連通,則M(G)＞M(G-u);M(G)＞M(G-e).

引理4[1]如果圖G是一個森林,則μ(G,x)=Φ(G,x).

引理5 對任意的樹T,則有M(T)=λ1(T).

證由引理4結論顯然成立.

定義1[3]設圖G的頂點序列為x1,x2,…,xk,若滿足：

(i)除x1與xk有可能相同外,其余xi互不相同;

(ii)頂點度d(xi)滿足d(x1)≥3,d(x2)=…=d(xk-1)=2(除非k=2),d(xk)≥3;

(iii)對于i=1,2,…,k-1,有xi與xi+1相鄰,

則稱x1,x2,…,xk是圖G的一條內部路.

引理6[4]設Gxy是由剖分G中的邊xy得到的圖,則有

(i)若xy不屬于G的內部路,且G≠Cn,則λ1(Gxy)＞λ1(G);

(ii)若xy屬于G的內部路,且G≠Un(n≥6),則λ1(Gxy)＜λ1(G).

引理7 設uv是樹G的任意一條邊,則

(i)若uv不屬于G的內部路,則M(Guv)＞M(G);

(ii)若uv屬于G的內部路,且G≠Un(n≥6),則M(Guv)＜M(G).

證由引理5,引理6可得結論成立.

引理8[5]若G是連通圖,則

(i)M(G)＜2當且僅當G∈Ω1={K1,Pn,Cn,T(1,1,n),T(1,2,i)(2≤i≤4),Q(2,1)};

(ii)M(G)=2當且僅當G∈Ω2={K1,4,T(2,2,2),T(1,3,3),T(1,2,5),In,Q(2,2),Q(3,1)}.

引理9[6]設G是一連通圖,則當且僅當G是下列圖之一：

(i)T(a,b,c)其中a=1,b=2,c＞5或a=1,b＞2,c＞3或a=b=2,c＞2或a=2,b=c =3;

(ii)T(1,a,b,c,1)其中(a,b,c)∈{(1,1,2),(2,4,2),(2,5,3),(3,7,3),(3,8,4)}或a≥1, b≥b＊(a,c),c≥1,這里(a,c)≠(1,1)且

(iii)Q(2,n)(n≥3),或Q(m,1)(m≥4),或Q(3,2).

定義2[1]設G是一個連通圖,u∈V(G),定義圖G關于點u的路樹T(G,u)如下：

V(T(G,u))={G中從點u開始的路(包括點u)};

E(T(G,u))={(P1,P2)|P1,P2是G中從點u開始的路,且一條路是另一條路的極大真子路}.

引理10[7]對任意連通圖G,M(G)等于它的任意頂點路樹的最大特征根.

引理11[8]圖∪

i∈ACi是匹配唯一的,其中A是大于等于3的整數組成的可重集.

引理12[9]設G有n個頂點n-1條邊,且G的度序列π(G)={1,1,1,3,2,…,2},如果μ(G,x)=μ(H,x),則H的度序列為π(H)={1,1,1,3,2,…,2},或π(H)={0,2,…,2}.

引理13[10]Q(m,n)～Q(n+1,m-1).

引理14[11](i)P2m+1～Pm∪Cm+1(m≥2);T(1,1,n)～K1∪Cn+2(n≥1);

(ii)若m+1=2n+1對某個正整數n成立,則此時Pm的所有匹配等價圖是：

特別地,僅當m+1=3×2n-1時,Pm的匹配等價圖才含有P2分支P2∪C3∪C6∪…∪C3×2n-2

證由引理15,比較各式兩邊匹配最大根可得結論成立.

3 主要結果及其證明

引理17 對任意正整數t≤n1,若max{b,d}≥t,則有M(T(1,t,n1))＜M(T(1,b,n2,d,1)).

證不妨設max{b,d}=b≥t,由引理3和引理7可得

[1] Godsil C D.Algebraic Combinatorics[M].New York：Chapman and Hall,1993.

[2] Bondy J A,Murty U S R.Graph Theory with Applications[M].North-Holland：Amsterdam,1976.

[3] Cvetkovic D,Rowlinson P.The largest eigenvalue of a graph：A survey[J].Linear and Multilinear Algebra,1990, 28(1,2)：3-33.

[4] Cvetkovic D M,Doob M,Gutman I,Torgaser A.Recent result in the theory of graph spectra[M].New York： Elsevier Science Publishers,1988.

[5] 馬海成.匹配根對圖的刻畫[J].曲阜師范大學學報,2001,27(1)：33-36.

[7] 馬海成,趙海興.小度數或大度數圖中的匹配唯一圖[J].數學研究與評論,2004,24(2)：369-373.

[8] 郭知熠,俞玉森.關于兩類圖的匹配唯一性[J].應用數學,1989,2：25-32.

[9] 申世昌.T形樹的匹配唯一性[J].數學研究,1999,32(1)：86-91.

[10] 李改楊.幾類圖的匹配唯一性[J].應用數學,1993,5(3)：53-59.

[11] 馬海成.兩類圖的匹配等價類[J].數學研究,2000,33(2)：218-222.

[12] 張海良.幾類圖的匹配多項式之間的關系與一類圖的匹配等價圖[J].純粹數學與應用數學,2007,23(2)：178-182.Ci)(n≥3 andAis multiset with integer numbers of more than or equal to 3 as its elements),by the properties of graph’s matching polynomial and it’s maximum roots.

On the Matching Equivalent Classes ofT(2,2,n)∪(Ci)

Z HA N Fu-qin, QIAO You-f u

(Department of Mathematics,Hechi University,Yizhou,Guangxi 546300,China)

matching polynomial;matching equivalence;matching uniqueness;the maximum real roots of graph’s matching polynomial

We completely characterize the matching equivalent classes ofT(2,2,n)∪(

O157.5

A

1672-1454(2011)03-0053-06

2008-08-21;[修改日期]2008-12-24

廣西教育廳科研項目(201010LX471;201010LX495);河池學院科研項目(2009A-N004;2008QS-N007,N008)