吳羅義

(武夷學院 數(shù)學與計算機學院,福建 武夷山 354300)

0 引言

定義：對于序列圖G的某一序列值，如果存在整數(shù)k，使得每條邊uv∈E(G)有

f(u)≤k,f(v)>k或者f(u)>k,f(v)≤k

則稱這種序列標號為序列平衡標號，稱為此種標號的特征.

1 引理

引理1[6]：若q條邊樹T有序列平衡標號f，特征為k，且f(vi)=0,f(vj)=k+1，f(vk)=k,f(vl)=q,則vivj∈E(T)且為邊標號最小的邊，vkvl∈E(T)且為邊標號最大的邊．

證顯然f：V(T)→{0,1,2,…，q}為單射，

因為φ是T的序列平衡標號，所以φ(vi)+φ(vj)為連續(xù)的不同的整數(shù)片段

當vivj∈E(T)時，由f導出的邊標號f′滿足

f′(vivj)=f(vi)+f(vj)=q+2k+1-(φ(vi)+φ(vj))

所以，f(vi)+f(vj)為連續(xù)的不同的整數(shù)片段.

根據(jù)f的標號情況，顯然對應的特征為k.

引理3[5](一般圖標號)：φ是G的序列標號當且僅當f=m-φ是G的序列標號.其中f(u)=(m-φ)(u)=m-φ(u),u∈V(G)

推論1：若φ是q邊樹T的序列平衡標號，對應的特征為k，則f=q-φ也是T的序列平衡標號，且特征為q-k-1.

2 主要定理

定理1若T1，T2分別具有某兩個序列平衡標號f1,f2的樹，邊數(shù)分別為q1,q2，對應的特征分別為k1,k2，那么將T1中標號為0，k1,k1+1,q1的任意頂點與T2中標號為0，k2,k2+1,q2的任意頂點粘接，所得的樹T*為具有序列平衡標號的序列樹．

證根據(jù)引理2和推論1可知：存在由fi導出的新標號，使得Ti在fi下標號為0，ki,ki+1,qi的頂點在導出的新標號下對應為0，且導出的新標號也是序列平衡標號．所以要證明命題成立，只需證：“T1中標號為q1的頂點與T2中標號為0的頂點粘接所得的樹T*為具有序列平衡標號的序列樹．”成立即可.

Ti可劃分為Xi={x∈V|f(x)≤ki}和Yi={x∈V|f(x)>ki}．

定義T*的頂點標號φ：

樹T*的邊為q1+q2，頂點為q1+q2+1.

易驗證，φ為V(T)→{0,1,2,…，q1+q2}的單射.

下面證明由φ導出的T*邊標號為q1+q2個連續(xù)的不同的整數(shù).

因為f1是T1的序列平衡標號，特征為k1，結(jié)合引理1，可得T1的q1條邊在f1導出的邊標號為q1個連續(xù)不同整數(shù){k1+1,k1+2,…,q1+k1}；同理可得T2的q2條邊在f2導出的邊標號為q2個連續(xù)不同整數(shù){k2+1，k2+2，…，q2+k2}.

xy∈T1(x∈X1,y∈Y1)，則由φ導出的邊標號φ(x)+φ(y)=f1(x)+f1(y)+q2-k2，所以T1的q1條邊在φ導出的邊標號為q1個連續(xù)不同整數(shù){q2+k1-k2+1,q2+k1-k2+2,…，q1+q2+k1-k2}；

xy∈T2(x∈X2,y∈Y2)，則由φ導出的邊標號為φ(x)+φ(y)=f2(x)+f2(y)+q1+q2+k1-2k2，所以T2的q2條邊在φ導出的邊標號為q2個連續(xù)不同整數(shù){q1+q2+k1-k2+1,q1+q2+k1-k2+2,…，q1+2q2+k1-k2}；

所以，φ導出T*的邊標號為q1+q2個連續(xù)的不同的整數(shù)

{q2+k1-k2+1,q2+k1-k2+2,…，q1+2q2+k1-k2}

所以，φ是T*的序列標號，取k=q2+k1-k2，由粘接方式，可把T二部劃分為：

X={x∈X1∪Y2|φ(x)≤q2+k1-k2}或Y={x∈X2∪Y1|φ(x)>q2+k1-k2}.

綜上定理成立．

定理2若T1，T2分別具有某兩個序列平衡標號f1,f2的樹，邊數(shù)分別為q1,q2，對應的特征分別為k1,k2，那么將T1中標號為0，k1,k1+1,q1的頂點與T2中標號為0，k2,k2+1,q2的頂點用一新邊連接起來，所得的樹T*為具有序列平衡標號的序列樹．

證根據(jù)定理1證明分析，只需證：“T1中標號為q1的任意頂點與T2中標號為0的任意頂點用一新邊連接起來所得的樹T*為具有序列平衡標號的序列樹．” 成立即可.

構(gòu)造所得的樹T*邊數(shù)為q1+q2+1，頂點為q1+q2+2.

Ti(i=1,2)可劃分為Xi={x∈Vi|fi(x)≤ki}和Yi={x∈Vi|fi(x)>ki}.

定義T的頂點標號φ

從φ的標號方式可知，最大的頂點標號為q1+q2+1并且各點標號不同，所以φ為V(T)→{0，1，…，q1+q2+1}的單射.

下面證明φ導出的T*邊標號為q1+q2個連續(xù)的不同的整數(shù).

仿照定理1證明可知T1的q1條邊在φ導出的邊標號為q1個連續(xù)不同整數(shù){k1+k2+2,k1+k2+3,…，q1+k1+k2+1}；T2的q2條邊在φ導出的邊標號為q2個連續(xù)不同整數(shù){q1+k1+k2+3,q1+k1+k2+4,…，q1+q2+k1+k2+2}.

根據(jù)連接方式可知新增加的邊標號為q1+k1+k2+2，

所以，φ導出T*的邊標號為q1+q2+1個連續(xù)的不同的整數(shù)

{k1+k2+2,k1+k2+3,…，q1+q2+k1+k2+2}.

所以，φ是Τ*的序列標號，取k=k1+k2+1，由粘接方式，可把T二部劃分為：

X={x∈X1∪Y2|φ(x)≤k}或Y={x∈X2∪Y1|φ(x)>k}.

綜上定理成立．

注：由定理1與定理2所生成的序列樹仍是序列平衡樹的，所以可以推廣到n棵序列平衡樹“連接”或“粘接”的情形.

根據(jù)標號可知C2n+1中的邊標號為連續(xù)整數(shù)片段{n,n+1,…，3n}；

每個ki(i=2n+1,2n+2,…，2n+m)與ci(i=0，1，…，2n)各點連接的邊共2n+1條，這2n+1條邊標號為

{3n+(j-1)·2n+j,3n+(j-1)·2n+j+1,…，3n+(j-1)·2n+j+2n},j=1,2,…，m

為連續(xù)整數(shù)片段.所以與ki鄰接的邊標號為連續(xù)整數(shù)片段{3n+1,3n+2，…，3n+2mn+m}.

綜上所述：則由φ導出的邊標號連續(xù)整數(shù)片段{n,n+1,…3n,3n+1,…，3n+2mn+m}.

例：具有圖1序列標號的兩棵樹T1,T2，將T1標號為最大的頂點與T2標號為最大的頂點粘接可得圖2的序列標號；將T1標號為最大的頂點與T2標號為最大的頂點粘接聯(lián)接可得圖3的序列標號.

圖1T1、T2樹的序列標號圖2T1與T2粘接的序列標號

[1] J.A.Gallian.A Dynamic Survey of Graph Labeling[J]．Electronic Journal of Combinatorics，2002，5：41～42．

[2]D.Jungreis and M.Reid，Labeling grids[J].Ars Combin.， 1992,34:167～182．

[3]馬克杰．優(yōu)美圖[M]．北京：北京大學出版社，1991．

[4]賀 丹，劉彥佩．樹積序列性及序列標號[J]．北方交通大學學報，2003，27(3)：46～49．

[5]朱振廣，徐美進，劉春峰．序列圖的一些必要條件與非序列圖類[J].遼寧工程技術大學學報，2007,26(2)：318～320．

[6]吳羅義，朱振廣，闞永志.一類序列樹的構(gòu)造[J].遼寧工業(yè)大學學報，2009,29(4)：268～271.

[7]M.Z.Youssef.Two general results on harmonious labelings[J].Ars Combin.，2003,(68)：225～230.

[8]張克民.某些圖論問題的進展[J].數(shù)學研究與評論，2007,7(3):563～575.

[9]王湘平.圖K4×C2的臨界群[J].吉林師范大學學報(自然科學版),2009,30(2):53～59.

[10]丁孝全.一類圖的序列標號[J].信陽師范學院學報,2007,13(3):251～253.