图Bn∪kD4的伴随等价图

赵绍玉，周仁静

(三明学院 数学与信息工程学院，福建 三明 365004)

1 基本定义和引理

定义1[1]G表示具有n个顶点的图,取:

定义2[1]图G的特征标定义如下：

在这里b1(G)和b2(G)分别表示h(G)的第二和第三项系数.

定义3[2]取b0(G),b1(G),b2(G)和b3(G)分别是h(G)的第1,2,3,4项系数,

那么图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 主要结果及其证明

定理1n,k,f是整数,图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,可以假设:

(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].甘肃联合大学学报:自然科学版,2010,24(2):1-5.