圖的對稱分割指數(shù)的界

李小麗，邵燕靈

(中北大學(xué) 理學(xué)院，山西 太原 030051)

0 引 言

本文討論的圖G均為簡單連通無向圖.設(shè)圖G=(V(G),E(G))為n階無向圖，其頂點集V(G)={v1,v2,…,vn}，邊集E(G)，|E(G)|=m，di為頂點vi的度，i=1,2,…,n； 用e=vivj表示其端點為vi,vj的邊，若其中di=1，則稱vi為懸掛點.
圖G的最小度記為δ，最大度記為Δ，用p表示圖G中懸掛點的個數(shù).

本文主要通過對圖G最大度Δ、最小度δ的奇偶性分類討論得到了圖的對稱分割指數(shù)SDD(G)的下界，然后，利用一些熟知的不等式給出了SDD(G)+ISDD(G),SDD(G)-ISDD(G),SDD(G)/ISDD(G)的關(guān)系.

1 對稱分割指數(shù)的下界

引理2[15]設(shè)圖G有m條邊，最小度為δ，最大度為δ+1，β表示圖G中滿足du+dv=2δ+1的邊uv∈E(G)的個數(shù)，則β是偶數(shù).

定理1設(shè)圖G有m條邊，最小度為δ，最大度為δ+1，β表示圖G中滿足du+dv=2δ+1的邊uv∈E(G)的個數(shù)，則

定理2設(shè)圖G有m條邊，最小度為δ，最大度為δ+1，則

證畢.

定理3設(shè)圖G有m條邊，最小度為δ，最大度為Δ>δ+1，記β0，β1，β2分別為G中的邊集A0={uv∈E(G)：du=δ,dv=Δ}，A1={uv∈E(G)：du=δ,δ

證畢.

定理4設(shè)圖G是n階連通圖，有m條邊，最小度為δ，最大度為Δ>δ+1，則

證明設(shè)A0，A1，A2，β0，β1，β2如定理3中所定義，由于G是連通圖，故A0非空，或A1與A2均非空.

若A1與A2均非空，則β1≥1，β2≥1，故由定理3得

證畢.

定理5設(shè)圖G是n階連通圖，有m條邊，最小度為δ，最大度為Δ>δ+1.

1) 若δ是偶數(shù)，則

SDD(G)≥2m+

2) 若Δ是偶數(shù)，則

SDD(G)≥2m+

證明設(shè)A0，A1，A2，β0，β1，β2如定理3中所定義.令m1為圖G中滿足du+dv=2δ的邊uv∈E(G)的邊數(shù)，n1為圖G中du=δ的頂點的個數(shù)，m2為圖G中滿足du+dv=2Δ的邊uv∈E(G) 的邊數(shù)，n2為圖G中du=Δ的頂點的個數(shù).因圖G是連通圖，故有n1δ-β0-β1=2m1，n2Δ-β0-β2=2m2.

若β0=1，則β1≥1，由定理3得

若β0=0，則β1≥2，β2≥1，由定理3得

SDD(G)≥2m+

若β0=1，則β2≥1，由定理3得

若β0=0，則β2≥2，β1≥1，由定理3得

SDD(G)≥2m+

證畢.

定理6設(shè)圖G是n階連通圖，有m條邊，最小度為δ，最大度為Δ>δ+1.

1) 若δ是偶數(shù)，則

2) 若Δ是偶數(shù)，則

因此，

2 對稱分割指數(shù)與反對稱分割指數(shù)的一些關(guān)系

定理7設(shè)圖G為n階樹，n≥3，則

當(dāng)且僅當(dāng)圖G為Pn時左邊等號成立，圖G為Sn時右邊等號成立.

du≥dv.

若圖G同構(gòu)Pn，則

SDD(Pn)+ISDD(Pn)=2g(2)+

若圖G不同構(gòu)Pn，此時圖G中的懸掛點P≥3，則

SDD(G)+ISDD(G)≥3g(2)+(n-4)g(1)=

SDD(G)+ISDD(G)-(SDD(Pn)+ISDD(Pn))≥

可得

(1)

當(dāng)且僅當(dāng)圖G同構(gòu)Pn時式(1)等號成立.

SDD(G)+ISDD(G)≤(n-1)g(n-1)=

(2)

當(dāng)且僅當(dāng)圖G同構(gòu)Sn時式(2)等號成立.證畢.

定理8設(shè)圖G為n階樹，n≥3，則

當(dāng)且僅當(dāng)G為Pn時左邊等號成立，圖G為Sn時右邊等號成立.

若圖G同構(gòu)Pn，則

SDD(Pn)-ISDD(Pn)=2g(2)+

若圖G不同構(gòu)Pn，此時圖G中的懸掛點P≥3，則

SDD(G)-ISDD(G)≥3g(2)+

SDD(G)-ISDD(G)-(SDD(Pn)-ISDD(Pn))≥

故

(3)

當(dāng)且僅當(dāng)圖G同構(gòu)Pn時式(3)等號成立.

SDD(G)-ISDD(G)≤(n-1)g(n-1)=

(4)

當(dāng)且僅當(dāng)圖G同構(gòu)Sn時式(4)等號成立.證畢.

定理9設(shè)圖G為n階連通圖，n≥3，則

當(dāng)且僅當(dāng)G為Sn時左邊等號成立，圖G為Kn時右邊等號成立.

(5)

當(dāng)且僅當(dāng)a1=a2=…=am時等式(5)成立.

因為

故

(6)

當(dāng)且僅當(dāng)圖G同構(gòu)Sn時式(6)等號成立.

(7)

只有式(5)，式(6)等號同時成立時，式(7)等號才成立，因此，當(dāng)且僅當(dāng)圖G同構(gòu)Sn時式(7)等號成立. 又因為

所以

(8)

當(dāng)且僅當(dāng)圖G同構(gòu)kn時式(8)等號成立. 證畢.