關于等價邊優美邊裂圖

溫一慧

(蘇州科技學院數理學院,江蘇 蘇州 215009)

0 引言

圖的標號問題一直是圖論中的熱點問題,多年來引起了許多學者的興趣和關注,新的問題也不斷被提出,并取得了不少成果[1-14].注意到對于一般的圖,其生成的邊裂圖有無窮多,由于沒有有效方法,要判斷這無窮多個邊裂圖的邊優美性是困難的,尤其是非均勻邊裂圖.本文引進等價邊優美邊裂圖的概念,闡述了等價邊優美邊裂圖的存在性,并舉例說明利用等價分類研究的方法,研究由某些圖生成的無窮多邊裂圖的邊優美性是可行的.

1 基本知識

定義1.1[1]設G=(V,E)是一個(p,q)簡單圖,雙射h:E(G)→{1,2,3,…,q},h的誘導映射如果h+也是雙射,則稱G為邊優美圖.否則稱為G非邊優美圖.

定義1.2[2]設G=(V,E)是一個(p,q)簡單圖,N是正整數集,映射f:E(G)→N,f(e)i=ki,ei∈E(G),ki∈N,定義G的邊裂圖SPE(G,f):令f(e)i=ki誘導的邊集.

p(e)i={ei1,ei2,…,eikieij與ei的端點關聯,j=1,2,…,ki},i=1,2,…,q,取,則稱SPE(G,f)為G的邊裂圖.

若定義中映射f:E(G)→N,f(e)i=n0,n0>0是某個給定的整數,i=1,2,…,q,則稱SPE(G,f)為G的均勻邊裂圖.否則稱為非均勻邊裂圖.

設G=K1,3,映射f:E(K1,3)→N,f(e)i=ni,i=1,2,3,為了討論的方面起見,也記為SPE(K1,3,f)為SPE(K1,3,f(n1,n2,n3)).

引理1.1[3]設G是一個(p,q)圖,則G是邊優美的必要條件是

q(q+1)≡ {0(mod p),P是奇數.p/2(mod p),P是偶數

2 主要結果

下面給出等價邊優美邊裂圖的概念.并以非均勻邊裂圖SPE(K1,3,f)為例,說明等價邊優美邊裂圖的存在性,利用等價分類方法討論其無窮非均勻邊裂圖邊優美性是可行的.

定義2.1 若邊裂圖G1與G2滿足V(G1)=V(G2),E(G1)≤ E(G2),且G1與G2有相同的邊優美性,則稱G1與G2是等價邊優美邊裂圖.

設{u0,u1,u2,u3}和{e1,e2,e3}={u0u1,u0u2,u0u3}分別是k1,3的頂點集和邊集,其中u0是k1,3的中心.下面討論中,設p=V(SPE(K1,3,f))=V(K1,3),q=E(SPE(K1,3,f)).

引理2.1 設n>1是任意整數,映射f:E(K1,3)→N,f(ei)=n,ei∈E(K1,3),i=1,2,3,則當且僅當n≡2(mod 4)或n≡3(mod 4),SPE(K1,3,f(n,n,n))是邊優美的.

證明 1)若n≡2(mod 4),不妨設n=4k+2,k=0,1,2,…,此時p=4,q=3n=3(4k+2),對集合X={1,2,…,q},為了討論方便,將其表成在模p意義下同余類[0],[1],[2],…,[p-1]的重集的形式:即

X={1,2,…,3(4k+2)}={(3k+2).[1],(3k+2).[2],(3k+1).[3],(3k+1).[0]}(mod4).分別構造f(ei)=n誘導的邊集p(ei)的標號集Xi,i=1,2,3如下

X1={(2k+1).[1],(2k+1).[3]},則f+(u1)=0;

X2={(2k+1).[0],(2k+1).[2]},則f+(u2)=2;

X3=X(X1∪X2)={(k+1).[1],(k+1).[2],k.[3],k.[0]},

由于在(mod 4)意義下,(k+1).[1]+(k+1).[2]+k.[3]+k.[0]=[1]+(k+1).[2],因此,若k是奇數,有f+(u3)=1,f+(u0)=3;若k是偶數,有f+(u3)=3,f+(u0)=1.所以當n≡2(mod 4),SPE(K1,3,f(n,n,n))是邊優美的.

2)若n≡3(mod 4),不妨設n=4k+3,k=0,1,2,…,此時q=3n=3(4k+3).當k=0,容易驗證SPE(K1,3,f(3,3,3))是邊優美的;若當k=1,2,…,令

Y={1,2,…,3(4k+3)}={(3k+3).[1],(3k+2).[2],(3k+2).[3],(3k+2).[0]}(mod4),構造邊集p(ei)的標號集Yi,i=1,2,3如下

Y1={(2k+1).[1],(2k+1).[3],[0]},有f+(u1)=0;

Y2={2(k+1).[0],(2k+1).[2]},有f+(u2)=2;

Y3=Y(Y1∪Y2)={(k+2).[1],(k+1).[2],(k+1).[3],(k-1).[0]},

由于在(mod 4)意義下,(k+2).[1]+(k+1).[2]+(k+1).[3]+(k-1).[0]=[1]+(k+1).[2],因此當k是奇數時,有f+(u3)=1,f+(u0)=3;若k是偶數,有f+(u3)=3,f+(u0)=1.所以當n≡3(mod 4),SPE(K1,3,f(n,n,n))是邊優美的.

3)若n≡0(mod 4)或n≡1(mod 4),由于此時q(q+1)≡0(mod 4),根據引理

1.1,SPE(K1,3,f(n,n,n))不是邊優美的.

定理2.1 對任意整數n>1,SPE(K1,3,f(n,3n,3n)),SPE(K1,3,f(n,2n,4n))與SPE(K1,3,f(n,n,n))是等價邊優美邊裂圖.

證明 先證明當且僅當n≡2(mod 4)或n≡3(mod 4),SPE(K1,3,f(n,3n,3n))是邊優美的.

1)若n≡2(mod 4),設n=4k+2,k=0,1,2,…,q=7n=7(4k+2).令

A={1,2,…,7(4k+2)}={(7k+4).[1],(7k+4).[2],(7k+3).[3],(7k+3).[0]}(mod4),由引理2.1中X的定義,有AX={(4k+2).[1],(4k+2).[2],(4k+2).[3],(4k+2).[0]},將AX分成如下兩個子集:A22={(4k+2).[1],(4k+2).[3]},A33={(4k+2).[0],(4k+2).[2]},注意到在(mod 4)意義下,(4k+2).[1]+(4k+2).[3]=[0],(4k+2).[0]+(4k+2).[2]=[0],因此構造SPE(K1,3,f(n,3n,3n))的標號集:A1=X1,A2=X2∪A22,A3=X3∪A33,其沒有改變引理2.1中的f+(u1),f+(u2),f+(u3),f+(u0)的值,所以SPE(K1,3,f(n,3n,3n))是邊優美的.

2)若n≡3(mod 4),設n=4k+3,k=0,1,2,…,有q=7n=7(4k+3).令

C={1,2,…,7(4k+3)}={(7k+6).[1],(7k+5).[2],(7k+5).[3],(7k+5).[0]}(mod4),由引理2.1中Y的定義,有CY={(4k+3).[1],(4k+3).[2],(4k+3).[3],(4k+3).[0]},將CY分成如下兩個子集:C22={(4k+3).[1],(4k+3).[3]},C33={(4k+3).[0],(4k+3).[2]},由于在(mod 4)意義下,(4k+3).[1]+(4k+3).[3]=[0],(4k+3).[0]+(4k+3).[2]=[2],因此構造SPE(K1,3,f(n,3n,3n))的標號集:C1=Y1,C2=Y2∪C22,C3=Y3∪C33,與引理2.1證明過程比較:f+(u3)與f+(u0)的值互換,f+(u1)和f+(u2)的值不變,所以SPE(K1,3,f(n,3n,3n))仍是邊優美的.

對于SPE(K1,3,f(n,2n,4n)),只需將上面證明中的A33的子集{(4k+2).[0]}與C33的子集 {(4k+3).[0]},分別并入A22和C22,運用同樣方法,可得SPE(K1,3,f(n,2n,4n))是邊優美的.

若n≡0(mod 4),或n≡1(mod 4),SPE(K1,3,f(n,3n,3n))和SPE(K1,3,f(n,2n,4n))不滿足邊優美的必要條件.

據定義2.1和引理2.1,對任意整數n>1,SPE(K1,3,f(n,3n,3n)),SPE(K1,3,f(n,2n,4n))與SPE(K1,3,f(n,n,n))是等價邊優美邊裂圖.

定理2.2 對任意整數n>1,SPE(K1,3,f(n,n,5n))與SPE(K1,3,f(n,n,n))是等價邊優美邊裂圖.

證明 事實上,若n≡2(mod 4),設n=4k+2,k=0,1,2,…,將SPE(K1,3,f(n,n,5n))與SPE(K1,3,f(n,n,n))比較,前者比后者的一條懸邊增加了4n條裂邊,增加的4n條裂邊的標號和是[0](在(mod 4)意義下),說明增加的4n條裂邊的標號不改變f+(u1)的值,i=0,1,2,3.

若n≡3(mod 4),設n=4k+3,k=0,1,2,…,不失一般性,設f(e3)=5n,由于SPE(K1,3,f(n,n,5n))比SPE(K1,3,f(n,n,n))增加了4n條裂邊,裂邊的標號和是(4k+3).[2](在(mod4)意義下),注意到4k+3是奇數,與引理2.1證明比較:f+(u3)與f+(u0)的值互換,f+(u1)和f+(u2)的值不變,所以SPE(K1,3,f(n,n,5n))仍是邊優美的.

引理2.2 對任意整數n≥1,SPE(K1,3,f(n,n,2n))不是邊優美的.

證明 由于q(q+1)≡0(mod 4),據引理1.1,SPE(K1,3,f(n,n,2n))不是邊優美的.

引理2.3 對任意整數n≥1,當且僅當n≡1(mod 4)或n≡2(mod 4),SPE(K1,3,f(n,n,3n))是邊優美的.

證明 若n≡1(mod 4),設n=4k+1,k=0,1,2,….q=5n=5(4k+1).令Z={1,2,…,5(4k+1)}={(5k+2).[1],(5k+1).[2],(5k+1).[3],(5k+1).[0]}(mod4),構造邊集p(ei)的標號集Zi,i=1,2,3如下

Z1={(4k+1).[0]},有f+(u1)=0;Z2={(4k+1).[2]},有f+(u2)=2;

Z3=Z(Z1∪Z2)={(5k+2).[1],k.[2],(5k+1).[3],k.[0]},

由于在(mod 4)意義下,(5k+2).[1]+k.[2]+(5k+1).[3]+k.[0]=[1]+k.[2],因此,當k是奇數,有f+(u3)=3,f+(u0)=1;當k是偶數,有f+(u3)=1,f+(u0)=3.

若n≡2(mod 4),設n=4k+2,k=0,1,2,….q=5n=5(4k+2).令

在課堂中引入英美文學的鑒賞，可以極大地提高學生的綜合素質與素養，通過老師的進一步講解，學生能夠更深入地了解英美文化中的豐富寓意。當代社會風氣普遍浮躁，學生也不例外。學生對人生、世界的看法往往不成熟，所以更需要從文學名著中汲取養分，致力于完善自身的素質。

D={1,2,…,5(4k+2)}={(5k+3).[1],(5k+3).[2],(5k+2).[3],(5k+2).[0]}(mod4),構造邊集p(ei)的標號集Di,i=1,2,3,如下

D1={(4k+2).[0]},有f+(u1)=0;D2={(4k+2).[3]},有f+(u2)=2;D3=D(D1∪D2)={(5k+3).[1],(5k+3).[2],k.[3],k.[0]},

由于在(mod 4)意義下,(5k+3).[1]+(5k+3).[2]+k.[3]+k.[0]=3.[1]+(5k+3).[2],故當k是奇數,5k+3是偶數,有f+(u3)=3,f+(u0)=1;當k是偶數,5k+3是奇數,有f+(u3)=1,f+(u0)=3.

若n≡0(mod 4)或n≡3(mod 4),均有q(q+1)≡0(mod 4),據引理1.1,SPE(K1,3,f(n,n,3n))不是邊優美的.故當且僅當n≡1(mod 4)或n≡2(mod 4),SPE(K1,3,f(n,n,3n))是邊優美的.

定理2.3 對任意整數n≥1,SPE(K1,3,f(n,2n,2n))與SPE(K1,3,f(n,n,3n))是等價邊優美邊裂圖.

證明 由引理2.3的證明,若n≡1(mod 4),構造邊集p(ei)的標號集Ti,i=1,2,3如下,取

T1=Z1={4k+1).[0]},有f+(u1)=0;T2={4k+2).[1],4k.[2]},有f+(u2)=2;T3=Z(T1∪T2)={k.[1],(k+1).[2],(5k+1).[3],k.[0]},

由于在(mod 4)意義下,k.[1]+(k+1).[2]+(5k+1).[3]+k.[0]=[3]+(k+1).[2],因此,當k是奇數,有f+(u3)=3,f+(u0)=1;當k是偶數,有f+(u3)=1,f+(u0)=3.

若n≡2(mod 4),構造邊集p(ei)的標號集Si,i=1,2,3,如下,由引理2.3的證明,取

由于在(mod 4)意義下,(k+1).[1]+(k+1).[2]+(5k+2).[3]+k.[0]=[3]+(k+1).[2],因此當k是奇數,有f+(u3)=3,f+(u0)=1;當k是偶數,有f+(u3)=1,f+(u0)=3.

若n≡0(mod 4)或n≡3(mod 4),均有q(q+1)≡0(mod 4),SPE(K1,3,f(n,2n,2n))不是邊優美的.據定義2.1和引理2.3,對于n≥1,SPE(K1,3,f(n,2n,2n))與SPE(K1,3,f(n,n,3n))是等價邊優美邊裂圖.

引理2.4 設任意整數n≥1,則當且僅當n≡1(mod 4)或n≡3(mod 4),SPE(K1,3,f(n,n,4n))是邊優美的.

證明 若n≡1(mod 4),設n=4k+1,k=0,1,2,….q=6n=6(4k+1).令H={1,2,…,6(4k+1)}={(6k+2).[1],(6k+2).[2],(6k+1).[3],(6k+1).[0]}(mod4),構造邊集p(ei)的標號集Hi,i=1,2,3如下

H1={(4k+1).[0]},有f+(u1)=0;H2={(4k+1).[2]},有f+(u2)=2;H3=H(H1∪H2)={(6k+2).[1],(2k+1).[2],(6k+1).[3],2k.[0]},

由于在(mod 4)意義下,(6k+2).[1]+(2k+1).[2]+(6k+1).[3]+2k.[0]=[1]+(2k+1).[2],因此,有f+(u3)=3,f+(u0)=1.

若n≡3(mod 4),設n=4k+3,k=0,1,2,….q=6n=6(4k+3).令

R={1,2,…,6(4k+3)}={(6k+5).[1],(6k+5).[2],(6k+4).[3],(6k+4).[0]}(mod4),構造邊集p(ei)的標號集Ri,i=1,2,3如下,

R1={(4k+3).[0]},有f+(u1)=0;R2={(4k+3).[2]},有f+(u2)=2;R3=R(R1∪R2)={(6k+5).[1],2(k+1).[2],(6k+4).[3],(2k+1).[0]},

由于在(mod4)意義下,(6k+5).[1]+2(k+1).[2]+(6k+4).[3]+(2k+1).[0]=[1]+2(k+1).[2],因此,有f+(u3)=1,f+(u0)=3.

若n≡0(mod 4)或n≡2(mod 4),均有q(q+1)≡0(mod 4),SPE(K1,3,f(n,n,4n))不是邊優美的.故當且僅當n≡1(mod 4)或n≡3(mod 4),SPE(K1,3,f(n,n,4n))是邊優美的.

定理2.4 對任意整數n≥1,SPE(K1,3,f(n,2n,3n))與SPE(K1,3,f(n,n,4n))是等價邊優美邊裂圖.

證明 由引理2.4的證明,若n≡1(mod4),構造邊集p(ei)的標號集Fi,i=1,2,3如下

F1={(4k+1).[2]},有f+(u1)=2;F2={(4k+1).[1],(4k+1).[3]},有f+(u2)=0;F3=H(F1∪F2)={(2k+1).[1],(2k+1).[2],2k.[3],(6k+1).[0]},

由于在(mod 4)意義下,(2k+1).[1]+(2k+1).[2]+2k.[3]+(6k+1).[0]=[1]+(2k+1).[2],因此有f+(u3)=3,f+(u0)=1.

若n≡3(mod 4),構造邊集p(ei)的標號集Bi,i=1,2,3,如下,由引理2.4的證明,取

B1={(4k+3).[2]},有f+(u1)=2;B2={(4k+3).[1],(4k+3).[3]},有f+(u2)=0;B3=R(B1∪B2)={2(k+1).[1],2(k+1).[2],(2k+1).[3],(6k+4).[0]},

由于在(mod4)意義下,2(k+1).[1]+2(k+1).[2]+(2k+1).[3]+(6k+4).[0]=[1]+2(k+1).[2],因此有f+(u3)=1,f+(u0)=3.

若n≡0(mod4)或n≡2(mod4),均有q(q+1)≡0(mod4),SPE(K1,3,f(n,2n,3n)),不是邊優美的,故由定義2.1和引理2.4,SPE(K1,3,f(n,2n,3n))與SPE(K1,3,f(n,n,4n))是等價邊優美邊裂圖.

根據引理2.1~2.4及定理2.2,采用上面同樣的方法,可得

推論2.5 對任意整數n>1,t≥1,

1)若t≡1(mod4),則當且僅當n≡2(mod4)或n≡3(mod4),SPE(K1,3,f(n,n,tn))是邊優美的.

2)若t≡2(mod4),則SPE(K1,3,f(n,n,tn))不是邊優美的.

3)若t≡3(mod4),則當且僅當n≡1(mod4)或n≡2(mod4),SPE(K1,3,f(n,n,tn))是邊優美的.

4)若t≡0(mod4),則當且僅當n≡1(mod4)或n≡3(mod4),SPE(K1,3,f(n,n,tn))是邊優美的.

根據定理2.1和定理2.3,可得

推論2.6 對任意整數n>1,s≥1,

1)若s≡0(mod2),當且僅當n≡1(mod4)或n≡2(mod4),SPE(K1,3,f(n,sn,sn))是邊優美的.

2)若s≡1(mod2),當且僅當n≡2(mod4)或n≡3(mod4),SPE(K1,3,f(n,sn,sn))是邊優美的.

根據引理2.2和定理2.4,可得

推論2.7 設任意整數n≥1,r≥2,則

1)若r≡0(mod2),SPE(K1,3,f(n,(r-1)n,rn))不是邊優美的.

2)若r≡1(mod2),當且僅當n≡1(mod4)或n≡3(mod4),SPE(K1,3,f(n,(r-1)n,rn))是邊優美的.

根據引理2.1~2.4,定理2.1~2.4與推論2.5~2.7,可得

推論2.8 對任意整數n、s、t>1,SPE(K1,3,f(n,sn,tn))與SPE(K1,3,f(n,n,(s+t-1)n))是等價邊優美邊裂圖.

限于篇幅,討論從略.感興趣的讀者還可以繼續驗證下面的結果

定理2.9 設任意整數n>1,r≥1,則

1)若r≡0(mod4),則當且僅當n≡2(mod4)或n≡3(mod4),SPE(K1,3,f(n,n,n+r))是邊優美的.

2)若r≡1(mod4),則當且僅當n≡0(mod4)或n≡3(mod4),SPE(K1,3,f(n,n,n+r))是邊優美的.

3)若r≡2(mod4),則當且僅當n≡0(mod4)或n≡1(mod4),SPE(K1,3,f(n,n,n+r))是邊優美的.

4)若r≡3(mod4),則當且僅當n≡1(mod4)或n≡2(mod4),SPE(K1,3,f(n,n,n+r))是邊優美的.

定理2.10 若(s+t)≡r(mod 4),則SPE(K1,3,f(n,n+s,n+t))與SPE(K1,3,f(n,n,n+r))是等價邊優美邊裂圖,其中n>1,s≥1,t≥1是任意整數.

[1]Lo S P.On edge-graceful labelings of graphs[J].Congressus Numerantium,1985,50:231-241.

[2]Wen Y H,Lee S M,Sun H.On the supermagic edge-splitting extension of graphs[J].Ars Combinatoria,2006,79:115-128.

[3]Lee L M,Lee S M,Murty G.On edge-graceful labelings of complete graphs-solutions of Lo's conjecture[J].Congressum Numerantum,1988,62:225-233.

[4]嚴謙泰.積圖PnXPm的奇優美性和奇強協調性[J].系統科學與數學,2010,30(3):341-348.

[5]魏麗俠,張昆龍.幾類并圖的優美標號[J].中山大學學報:自然科學版,2008,47(3):10-13.

[6]程輝,姚兵,張忠輔.核圖與L(2,1)標號[J].蘭州大學學報:自然科學版,2008,44(2):94-97.

[7]溫一慧,康慶德.關于廣義蝶圖的平衡指標集[J].數學研究與評論,2009,29(2):202-212.

[8]Wen Y H,Lee S M,Su H H.On Z2⊕ Z2–magic Graphs[J].Congressus Numerantium,2009,199:13-31.

[9]Lee S M,Hokuen N,Wen Y H.On the edge-magic indices of(v,v+1)-graphs[J].Utilitas Mathematica,2007,72:97-110.

[10]劉家保,王林.一類圖的邊幻和標號及其算法[J].汕頭大學學報:自然科學版,2011,26(3):29-34.

[11]溫一慧.關于廣義輪圖的友好性[J].蘭州大學學報:自然科學版,2008,44(3):103-108.

[12]溫一慧.一類邊裂圖邊優美性的充要條件[J].數學的實踐與認識,2009,39(19):197-202.

[13]溫一慧.關于圖的一致平衡性[J].數學季刊,2010,25(4):565-571.

[14]溫一慧.組合.算法.理論與應用[M].蘭州:蘭州大學出版社,2006:359-378.