圖Bn∪kD4的伴隨等價圖

趙紹玉，周仁靜

(三明學(xué)院 數(shù)學(xué)與信息工程學(xué)院，福建 三明 365004)

1 基本定義和引理

定義1[1]G表示具有n個頂點的圖,取:

定義2[1]圖G的特征標定義如下：

在這里b1(G)和b2(G)分別表示h(G)的第二和第三項系數(shù).

定義3[2]取b0(G),b1(G),b2(G)和b3(G)分別是h(G)的第1,2,3,4項系數(shù),

那么圖G的第二特征標R2(G)定義如下：

很明顯,R2(Q5)=3，R2(Qn)=4.如果h(G,χ)=h(H,χ),那么R2(G)=R2(H).

引理1[1]G和H是兩個圖,如果h(G,χ)=h(H,χ)或者h1(G,χ)=h1(H,χ),那么R(G)=R(H).

引理3[1]圖G是有n個頂點的連通圖,那么：

1)R(G)≤1,等號成立當且僅當G?Pn或者G?k3；

2)R(G)=0當且僅當G∈{k1,Cn,Dn,Tl1,l2,l3},n≥4,li≥1；

引理5[3]1)R2(P1)=0,R2(P2)=-1,R2(Pn)=-2,n≥3;

3)R2(T1,1,1)=-1,R2(T1,1,n)=0,n≥2;

4)R2(D4)=0,R2(Dn)=1,n≥5,R2(F6)=5,R2(Fn)=4,n≥7.

引理6[2]R2(T1,l2,l3)=1,2≤l2≤l3,R2(Tl1,l2,l3)=2,2≤l1≤l2≤l3.

引理7[2]G是R1(G)=1的連通圖,并且q(G)≥n(G),那么R2(G)≥3,等號成立當且僅當:

特別的,有R2(B6)=4.

引理10[2]1)對所有的n≥2,m≥6,h1(Pn)|/h(Bm);

2)n≥2,m≥5,h1(Pn)|/h(Am)當且僅當m=3k+2,n=2,其中,k≥1.

引理11[5]1)對所有的m≥2,h(Kn)|/h(Dm)當且僅當m=5k+3,n=3,其中,k≥1.

2)對所有的n,m≥2,h(Pn)|h(Dm)當且僅當m=3k+2,n=2或者m=5k+3,n=4.

引理13[7-8]1)-4<β(Pn)<β(Pn-1),n≥2，β(Dn)<-4,n≥9;

2)-4<β(Cn+1)<β(Cn)<-3,β(Dn+1)<β(Dn),n≥4;

3)β(Dn)<β(Cn)<β(Pn),n≥5,β(D4)≈-3.4.

引理14[2]1)n≥6,h(Fn∪2K1)=h(Zn+2),h(Bn∪K1)=h(Vn+1);

2)n≥4,h(F2n+1∪K1)=h(Bn+2)h(Dn),h(B10)=h(A6)h(C4),h(B6)=h(Q6);

4)h(F9∪K1)=h(C4)h(B6),h(A9∪K1)=h(B6)h(T1,1,1);

5)h(F7)=h(P4)(x3+5x2+3x),h(F8)=h(P2)(x6+8x5+18x4+9x3+x2);

引理15[2]1)β(An)<β(An-1)<-4,β(Bn)<β(Bn+1),β(Fn)<β(Fn+1)n≥6;

2)β(Fn)<β(Bn)<-4,β(Fn)<β(Dm),β(Bn)<β(Dm)n≥6,m≥4;

3)β(Fn)=β(Bm)當且僅當n=2k+1,m=k+2,在這里k≥4;

4)β(B6)=β(A9)<β(A8)<β(B7)=β(A7)<β(B8)<β(B9)<β(B10)=β(A6),β(An)≤β(Bm)等號成立當且僅當m=n=7,m≥7,n≥7;

5)β(A6)=β(F17),β(A7)=β(F11),β(F9)<β(A8)<β(F10),β(A9)<β(F9),β(An)≤β(Fm)等號成立當且僅當m=n=9,n≥9,m≥9.

引理16[9]R2(Q5)=3,R2(Qn)=4,對所有的n≥6.

引理17[9]1)β(Qn+1)<β(Qn)≤-4,n≥5;β(Qn)<β(An),n≥6;

2)β(An)<β(T1,1,n-3),n≥5;β(Fn)<β(T1,1,n-3),n≥6.

引理18[9]對于n≥4,h(Cn∪K1)=h(T1,1,n-2),h(Dn∪K1)=h(T1,2,n-3).

2 主要結(jié)果及其證明

定理1n,k,f是整數(shù),圖G表示Bn∪kD4(n≥6),那么與G伴隨等價的圖H如下:

1)如果n≥6,那么H?Bn∪sD4∪(k-s)C4,0≤s≤k;

2)如果n=6,那么H?B6∪sD4∪(k-s)C4,H?Q6∪sD4∪(k-s)C4,0≤s≤k,或H?F9∪K1∪sD4∪(k-s-1)C4,0≤s

3)如果n=7,那么H?A7∪sD4∪(k-s)C4,0≤s≤k;

4)如果n=10,那么H?A6∪sD4∪(k-s+1)C4,0≤s≤k+1.

(1)

由引理10,11得到：

h(Pm)|/h(Bn),h(Pm)|/h(D4),

因為h(G)=h(H)，h1(P4)=h1(C3),所以由引理8可知H不包含Pm或者C3作為分支,由式(1)和引理1～3,可以推得：存在唯一的一個分支H1滿足R1(H1)=-1,并且R1(Hi)=0,對所有i≥2.不失一般性,由引理3,可以假設(shè):

(2)

(3)

因為n(G)=q(G),因此n(H)=q(H),所以由式(3)可得：

r+l+|Γ|=t

(4)

因為t≤1,并且t=1時當且僅當H1?Fv,所以可討論如下：

情形1t=1,很明顯H1?Fv,v≥6,利用式(4),知l≤1,由h(G)=h(H)和定義3得到：

R2(G)=R2(H),

利用引理4,5,7得到：

R2(G)=R2(H)≥R2(H1)+|S|-l

(5)

情形1.1G=B6∪kD4,那么R2(G)=R2(H)=4.

假如H1?F6.由式(4)和式(5),可得：

R2(F6)+|S|-l≤4,r=|S|=|Γ|=0,l=1.

由引理9可得：

由引理13,15以及β(D4)=-3.4,得到：β(G)=β(B6)>β(H)=β(F6).這與h(G)=h(H)相矛盾.

假如H1?Fv(v≥7)，可得:

R2(Fv)+|S|-l≤4

(6)

由引理5和式(4),可得：

r=|Γ|=0,l=|S|=1,或r=|Γ|=|S|=0,l=1,或l=|S|=|Γ|=0,r=1,或r=l=|S|=0,|Γ|=1.

若r=|Γ|=0,l=|S|=1.由式(2)和引理9,得:

(7)

由引理13～15，可得：

v=9,β(G)=β(B6),β(H)=β(F9).

那么由式(7)和引理14,得到:

由引理13,得：β(左)=β(D4)>β(右)=β(Duj),得到矛盾.

若r=|Γ|=|S|=0,l=1.由(2)和引理9,可得:

由引理13～15,得到：

v=9,β(G)=β(B6),β(H)=β(F9).

那么由式(7)和引理14,得到:

由引理13,得到：β(左)=β(D4)≠β(右)=β(Cni),得到矛盾.

若l=|S|=|Γ|=0,r=1,由式(2)和引理9,可得:

類似式(7)的證明,得到:

因為h(D4)=h(C4),所以上式成立當且僅當ni=4,|R|=k-f-1.這種情況下有：

H?F9∪K1∪fC4∪(k-f-1)D4.

若r=l=|S|=0,|Γ|=1.由引理9和式(2),得到:

由引理5和6,得到：Tl1,l2,l3∈{T1,1,c|c≥2},否則由引理4～7和式(2),可得：

l=|S|+|Γ|或者l=|S|+2|Γ|,

這與r=l=|S|=0,|Γ|=1矛盾.由引理13,15,17,可知：

v=9,β(G)=β(B6),β(H)=β(F9).

由引理14,得到：

由引理12,13,18可得到矛盾.

情形1.2G=Fv∪kD4(v≥7).由式(5)、引理8和h(G)=h(H)，可得：

R2(G)=R2(H)=3≥R2(H1)+|S|-l

(8)

假如H1?F6.由式(6)、引理8和h(G)=h(H)，可得：l≥2+|S|,這與l≤1矛盾.

假如H1?Fv(v≥7).由式(6)、引理8和h(G)=h(H)，可得：

l=1,r=|S|=|Γ|=0,

由式(2)得到：

由引理15,上式成立當且僅當n=k′+2,v=2k′+1(k′≥5).因此由引理14可得：

利用引理13,得到：

β(左)=β(D4)>β(右)=β(Dk').

因此情形1.2不成立.

情形2t=0.由式(2)和式(4),得：

r=l=|Γ|=0,R2(G)=R2(H)=R2(H1)+|S|

(9)

情形2.1G=B6∪kD4,由引理5,可得：R2(G)=R2(H)=4;由引理7,定義3,引理16和式(9)可得：

H1∈{Q5,At,Bv|t≥5,v≥7}而且|S|=1或者H1∈{Qv,B6|v≥6}并且|S|=0.

若H1?B6，可得：

由引理13,上式成立當且僅當ni=4,|R|=k-f.此種情況,得到：

H?B6∪fD4∪(k-f)C4.

若H1?Qv(v≥6)，可得：

由引理13,15得：β(左)=β(B6),β(右)=β(Qv).利用引理14,兩邊最小實根相等,得到：

由引理13和h(D4)=h(C4),上式成立當且僅當ni=4,|R|=k-f.此種情況,得到：

H?Q6∪fD4∪(k-f)C4.

若H1?Q5，可得：

由引理13,15得：β(左)=β(B6)<β(右)=β(Duj).與h(G)=h(H)矛盾.

若H1?Bv(v≥7)，可得:

由引理13,15得：β(左)=β(B6)<β(右)=β(Bv)(v≥7).與h(G)=h(H)矛盾.

若H1?At(t≥5)，可得:

由引理13,15和h(D4)=h(C4),t=9.再由引理14得:

利用引理13,分別比較兩邊的最小實根,都可得到矛盾.

如果ni≠4,利用引理13,比較兩邊的最小實根,也可得到矛盾.

情形2.2G=Bn∪kD4(n≥7).由引理7,定義3和式(9),可得：

R2(G)=R2(H)=3,H1∈{Q5,At,Bv|t≥5,v≥7}并且|S|=0.

若H1?Q5，可得:

因為β(Q5)=-4,所以由引理13,15得β(左)=β(Bn)<β(右)=β(Cni).與h(G)=h(H)矛盾.

若H1?At(t≥5)，可得:

(10)

由引理15得t=7,如果n=7,t=6,如果n=10.

如果n=7,那么t=7,由引理14和式(10)得:

因為h(D4)=h(C4),所以由引理13～15,得上式成立當且僅當ni=4,|R|=k-f.此種情況,得到：

H?A7∪fD4∪(k-f)C4.

如果n=6,那么t=10,類似上面的證明可得：

因為h(D4)=h(C4),所以由引理13～15,得上式成立當且僅當ni=4,|R|=k-f+1.此種情況,得到：

H?A6∪fD4∪(k-f+1)C4.

若H1?Bv(v≥7)，可得：

由引理13,15得β(左)=β(B6),β(右)=β(Bv)(v≥7).如果β(左)=β(右),那么n=v.由于h(D4)=h(C4),所以由引理13～15,得上式成立當且僅當ni=4,|R|=k-f.

由此得到H?Bn∪fD4∪(k-f)C4.

定理證畢.

[1] Liu R.Adjoint polynomials and chromatically unique graphs[J].Discrete Math,1997,172:85-92.

[2] Zhao H,Li X,Liu R,et al.On the Algebraic Properties of the Adjoint Polynomials and the Chromaticity of Two Classes of Graphs[D].The Netherlands, Hǒhrmann Print Service,2005.

[3] Dong F M,Koh K M,Teo K L,et al.Two invatiants of adjointly equivalent graphs[J].Audtralasian Combin,2002,25:167-174.

[4] Zhao H,Liu R.The necessary and sufficient condition of chromatic uniquenenss of Bn[J].Acta Scientiatum Naturalium Universities Neimongol,2003,34(1):1-3.

[5] Shouzhong W,Liu R.Chromatic uniqueness of the complements of cycle and D_n[J].Math Res Exposition,1998，18:296-199.

[6] Chengfu Y,Jian Y.The chromatically equivalent depiction and the chromatically unique condition of the complement of P_l∪C_m∪D_n[J].Journal of Shandong University,2006,41(1):24-29.

[7] Zhao H,Huo B,Liu R.Chromaticity of paths[J].Math Study,2000,33:345-353.

[8] Zhao H,Liu R.The necessary and sufficient condition of theirreducible Paths[J].Northeast Normal University,2001,33(2):18-21.

[9] 趙紹玉,尤垂桔.與圖An∪Dm的補圖色等價的圖[J].甘肅聯(lián)合大學(xué)學(xué)報:自然科學(xué)版,2010,24(2):1-5.