復(fù)合樹(shù)的Felicitous性質(zhì)

張明軍，楊思華，姚兵

(1. 蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院，甘肅 蘭州 730020；2. 蘭州財(cái)經(jīng)大學(xué)隴橋?qū)W院，甘肅 蘭州 730101；3. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

復(fù)合樹(shù)的Felicitous性質(zhì)

張明軍1，楊思華2，姚兵3

(1. 蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院，甘肅 蘭州 730020；2. 蘭州財(cái)經(jīng)大學(xué)隴橋?qū)W院，甘肅 蘭州 730101；3. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

將多個(gè)具有集有序 Felicitous 性質(zhì)的樹(shù)上的點(diǎn)與一棵集有序優(yōu)美樹(shù)上的點(diǎn)重合，構(gòu)造出一棵較大的復(fù)合樹(shù), 經(jīng)研究計(jì)算, 該復(fù)合樹(shù)具有集有序 Felicitous 性質(zhì)。

復(fù)合樹(shù); 集有序 Felicitous 標(biāo)號(hào); 集有序優(yōu)美標(biāo)號(hào)

圖的標(biāo)號(hào)廣泛應(yīng)用于編碼理論、通訊網(wǎng)絡(luò)、物流、同步機(jī)碼設(shè)計(jì)、無(wú)線電頻道分配和讀取DNA序列等領(lǐng)域。 優(yōu)美圖是圖的標(biāo)號(hào)研究中十分重要的課題之一。1966年, Rosa[1]提出了一個(gè)猜想：每一棵樹(shù)都是優(yōu)美樹(shù)。后來(lái)，Bermond[2]又提出了猜想：所有龍蝦樹(shù)都是優(yōu)美樹(shù)。關(guān)于這兩個(gè)猜想已經(jīng)有了很多結(jié)果, 但是一直沒(méi)有徹底的解決。Lee等[3]于 1991 年提出了猜想：每一棵樹(shù)都是 Felicitous 樹(shù)。該猜想與優(yōu)美樹(shù)猜想具有同等的理論價(jià)值, 而且具有相同的難度, 都是 NP-hard 問(wèn)題[4-13]。對(duì)于數(shù)學(xué)猜想的進(jìn)攻, 導(dǎo)致圖的標(biāo)號(hào)迅速發(fā)展成為當(dāng)今圖論學(xué)科中十分活躍的分支。

1 預(yù)備知識(shí)

本文涉及的圖均為有限、無(wú)向簡(jiǎn)單圖。文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均來(lái)自文獻(xiàn)[14]。為敘述簡(jiǎn)便，我們把一個(gè)有p個(gè)頂點(diǎn)q條邊的連通圖記為(p,q)-圖。記號(hào)[m,n]表示非負(fù)整數(shù)集合{m,m+1,m+2,…,n}，其中m和n均為整數(shù)，且滿足0≤m

定義1 設(shè)G是(p,q)-圖，若存在一個(gè)單射f:V(G)→[0,q]，使得邊標(biāo)號(hào)集合{f(uv)|uv∈E(G)}=[0,q-1]，其中邊標(biāo)號(hào)為f(uv)=f(u)+f(v)(modq)，那么稱G是Felicitous圖，并稱f是G的一個(gè)Felicitous 標(biāo)號(hào)。進(jìn)一步，設(shè)(X,Y)是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，如果G有一個(gè)Felicitous 標(biāo)號(hào)f，使得

max{f(x)|x∈X}

(以下簡(jiǎn)記為f(X)

則稱G是集有序 Felicitous 圖，也稱f是G的一個(gè)集有序 Felicitous 標(biāo)號(hào)。

對(duì)于定義1中的圖G和Felicitous標(biāo)號(hào)f，以下簡(jiǎn)記頂點(diǎn)標(biāo)號(hào)集合為f(V(G))={f(u)|u∈V(G) }，邊標(biāo)號(hào)集合為f(E(G))={f(u)+f(v)|uv∈E(G) }，以及f(E(G))(modq)={f(uv)|uv∈E(G) }。

定義2 設(shè)G是(p,q)-圖，若存在一個(gè)單射f:V(G)→[0,q]，使得邊標(biāo)號(hào)集合{f(uv)|uv∈E(G) }=[1,q]，其中邊標(biāo)號(hào)為f(uv)=|f(u)-f(v)|，那么稱G是優(yōu)美圖，并稱f是G的一個(gè)優(yōu)美標(biāo)號(hào)。進(jìn)一步，設(shè)(X,Y)是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，若G有一個(gè)優(yōu)美標(biāo)號(hào)f，使得f(X)

定義3 設(shè)T,H1,H2,…,Hp是樹(shù)，|V(T)|=p，V(T)={wi|i∈[1,p] }，|V(Hi)|=n，|V(Hi)|={ui,j|i∈[1,p],j∈[1,n] }，將T的頂點(diǎn)wi(i∈[1,p])與樹(shù)Hi中的一個(gè)ui,j0(j0∈[1,n])重合，得到的圖G叫做復(fù)合樹(shù)，特記為G=[T;H1,H2,…Hp]。

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

定理1 設(shè)樹(shù)H1,H2,…,H|V(T)|有集有序 Felicitous 標(biāo)號(hào)，樹(shù)T是集有序優(yōu)美樹(shù)，且其頂點(diǎn)集二部劃分(X,Y)滿足||X|-|Y||≤1，則復(fù)合樹(shù)[T;H1,H2,…,H|V(T)|]具有集有序 Felicitous 標(biāo)號(hào)。

證明根據(jù)定理假設(shè), 樹(shù)T是有p個(gè)頂點(diǎn)的集有序優(yōu)美樹(shù)，其頂點(diǎn)集二部劃分為(X,Y)，其中||X|-|Y||≤1，X={w1,w2,…wl}，Y={wl+1,wl+2,…wp}。樹(shù)T有一個(gè)集有序優(yōu)美標(biāo)號(hào)f，使得f(wi)=i-1，i∈[1,p]，并且f(X)

令|V(Hk)|=n，則有s+t=n,且有

利用f定義T的一個(gè)標(biāo)號(hào)f′如下：f′(wi)=f(wi)+1=i，i∈[1,p]。由p的奇偶性來(lái)定義復(fù)合樹(shù)[T;H1,H2,…Hp]的一個(gè)標(biāo)號(hào)h。

情形Ⅰ 當(dāng)p=2β+1時(shí)，從而有||X|-|Y||=1。令|X|=|Y|+1。我們定義復(fù)合樹(shù)[T;H1,H2,…Hp]的標(biāo)號(hào)h如下：

(i) 當(dāng)k∈[1,β+1]時(shí)，令

n(k-1)+i-1，i∈[1,s];

n(β+k-1)+s+j-1，j∈[1,t]

(ii) 當(dāng)l∈[β+2,2β+1]時(shí), 令

n(3β+2-l)+s-i，i∈[1,s]；

n(2β+2-l)-j，j∈[1,t]

經(jīng)過(guò)計(jì)算得h(V([T;H1,H2,…,H2β+1]))=

[0,n(2β+1)-1]，且有

{h(uk,i):k∈[1,β+1],i∈[1,s]}∪{h(vl,j):

l∈[β+2,2β+1],j∈[1,t]}=

[0,nβ+s-1]=X*；

{h(vk,j):k∈[1,β+1],

j∈[1,t]}∪{h(ul,i):l∈[β+2,2β+1],

i∈[1,t]}=[nβ+s，n(2β+1)-1]=Y*

注意到，若(X*,Y*)是復(fù)合樹(shù)[T;H1,H2,…Hp]的頂點(diǎn)集二部劃分，則有h(X*)

下面，證明標(biāo)號(hào)h是復(fù)合樹(shù)[T;H1,H2,…Hp]的集有序Felicitous 標(biāo)號(hào)。

當(dāng)k∈[1,β+1]，i∈[1,s]和j∈[1,t]時(shí)，Hk的每一條邊uk,ivk,j滿足

h(uk,ivk,j)=h(uk,i)+h(vk,j)=

n(β+2k-2)+s+i+j-2，

n(β+2k-1)+s-2]

當(dāng)l∈[β+2,2β+1]，i∈[1,s]和j∈[1,t]時(shí)，Hl的每一條邊ul,ivl,j滿足

h(ul,ivl,j)=h(ul,i)+h(vv,j)=

n(5β-2l+4)+s-i-j，

n(5β-2l+4)+s-2],

h(E(H1,H2,…,H2β+1))=

[nβ+s,n(3β+1)+s-2]N*

此處

N*=[n(β+1)+s-1,

n(β+2)+s-1,n(β+3)+s-1,…,

n(3β-1)+s-1,3nβ+s-1]

1) 對(duì)固定的i0∈[1,s]，將Hm(m∈[1,2β+1])的頂點(diǎn)um,i0與樹(shù)T的頂點(diǎn)wm重合。對(duì)k∈[1,β+1]，l∈[β+2,2β+1]，關(guān)于復(fù)合樹(shù)[T;H1,H2,…H2β+1]的邊wkwl有

f′(wkwl)=f′(wk)+f′(wl)=h(uk,i0)+

h(ul,i0)=n(3β+k-l+1)+s-1

經(jīng)過(guò)計(jì)算得

f′(wkwl)∈[n(β+1)+s-1,n(β+2)+s-1,

n(β+3)+s-1,…,n(3β-1)+s-1,

3nβ+s-1]=N*

2) 對(duì)固定的j0∈[1,t]，將Hm(m∈[1,2β+1])的頂點(diǎn)vm,j0與樹(shù)T的頂點(diǎn)wm重合。對(duì)k∈[1,β+1]，l∈[β+2,2β+1]，計(jì)算復(fù)合樹(shù)[T;H1,H2,…H2β+1]的邊wkwl，得到

f′(wkwl)=f′(wk)+f′(wl)=

h(vk,j0)+h(vl,j0)=

n(3β+k-l+1)+s-1

經(jīng)過(guò)計(jì)算得

f′(wkwl)∈
[n(β+1)+s-1,n(β+2)+s-1,
n(β+3)+s-1,…,n(3β-1)+s-1,
3nβ+s-1]=N*

綜上得，邊標(biāo)號(hào)集合h(E([T;H1,H2,…Hp]))=[nβ+s,n(3β+1)+s-2]。因此，

h(E([T;H1,H2,…Hp]))·
(modn(2β+1)-1)=[0,n(2β+1)-2]，
h(V([T;H1,H2,…H2β+1]))=[0,n(2β+1)-1]

以及

h(X*)

故當(dāng)p是奇數(shù)時(shí)，標(biāo)號(hào)h是復(fù)合樹(shù)[T;H1,H2,…Hp]的集有序 Felicitous 標(biāo)號(hào)。

情形Ⅱ 當(dāng)p=2β時(shí)，則有||X|-|Y||=0。定義標(biāo)號(hào)h如下：

(i) 當(dāng)k∈[1,β]時(shí), 令

h(uk,i)=n(k-1)+i-1，i∈[1,s]；

h(vk,j)=n(β+k-1)+j-1，j∈[1,t]

(ii) 當(dāng)l∈[β+1,2β]時(shí), 令

h(ul,i)=n(3β+1-l)-i，i∈[1,s]；

h(vl,j)=n(2β+1-l)-j，j∈[1,t]

用與奇數(shù)情形相同的方法, 可得到邊標(biāo)號(hào)集合

h(E([T;H1,H2,…Hp]))(mod 2nβ-1)=

[0,2nβ-2]

綜合情形 1 和情形 2 的討論, 本定理得證。(圖1與圖2是解釋定理1的兩個(gè)例子)

圖1 解釋定理1的一個(gè)例子Fig.1 An example for illustrating Theorem 1

圖2 解釋定理1的另一個(gè)例子Fig.2 Another example for illustrating Theorem 1

[1] ROSA A. On certain valuations of the vertices of a graph [J]. Theory of Graphs, 1967: 349-355.

[2] BERMOND J C. Graceful graphs, radio antennae and French windmills [J]. Graph Theory & Combinatorics, Pitman London, 1979, 34: 18-37.

[3] LEE S M, SCHMEICHEL E, SHEE S C. On felicitous graphs [J]. Discrete Mathematics, 1991, 93(2/3): 201-209.

[4] GALLIAN J A. A dynamic survery of graph labeling [J]. The electronic journal of combinatorics, 2009, 12: 42-43.

[5] MANICKAM K, MARUDAI M, KALA R. Some results on felicitous labeling of graphs [J]. Journal of Combinatorial Mathematics & Combinatorial Computing, 2012, 81: 273-279.

[6] GNANAJOTHI R B. Topics in graph theory [D]. Madurai: Madurai Kamaraj University, 1991.

[7] YAO B, CHENG H, YAO M, et al. A note on strongly graceful trees [J]. Ars Combinatoria, 2009, 92:155-169.

[8] GRAHAMS R L, SLOANE N J A. On additive bases and harmonious graphs [J]. Siam Journal on Algebraic & Discrete Methods, 2006, 1(1): 382-404.

[9] ZHOU X Q, YAO B, CHEN X E, et al. A proof to the odd-gracefulness of all lobsters [J]. Ars Combinatoria, 2012, 103: 13-18.

[10] 唐保祥, 任韓. 2類優(yōu)美圖的冠的優(yōu)美標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 54(5): 24-27.

TANG B X，REN H. Graceful labeling of the corona for two kinds of graceful graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(5): 24-27.

[11] 趙喜楊, 姚兵. 探討樹(shù)的(k,d)-邊魔幻全標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(6): 67-73.

ZHAO X Y, YAO B. Probing (k,d)-edge magic total labellings of trees [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(6): 67-73.

[12] 張明軍，趙喜楊，姚兵.(2m+1,1)-p-樹(shù)的二分強(qiáng)優(yōu)美性和二分強(qiáng)奇優(yōu)美性[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 2016, 39(3): 419-428.

ZHANG M J, ZHAO X Y, YAO B. On bipartite strongly gracefulness and bipartite strongly odd-gracefulness of (2m+1,1)-p-trees [J]. Acta Mathematicae Applicatae Sinica, 2016, 39(3): 419-428.

[13] 吳躍生. 圖Fn,4(r1,r2,…,r3n+1)的交錯(cuò)標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(4):11-14.

WU Y S. The alternating labeling of the graphFn,4(r1,r2,…,r3n+1)[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(4):11-14.

[14] BONDY J A, MURTY U S R. Graph theory with applications [M]. London: The MaCmillan Press ltd, 1976.

TheFelicitouspropertyofcompositetrees

ZHANGMingjun1,YANGSihua2,YAOBing3

(1. School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China;2. Longqiao college, Lanzhou University of Finance and Economics, Lanzhou 730101, China;3. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China)

Multiple trees with set-ordered Felicitous property are coupled with a vertex on set-ordered graceful trees, and a larger composite tree is constructed. It is shown that, the composite tree has set-ordered Felicitous property.

composite trees; set-ordered felicitous labelling; set-ordered graceful labelling

10.13471/j.cnki.acta.snus.2017.06.008

2017-03-01

國(guó)家自然科學(xué)基金(61363060, 61662066)；蘭州財(cái)經(jīng)大學(xué)高等教育教學(xué)改革研究重點(diǎn)項(xiàng)目(LJZ201707)；甘肅省高等學(xué)?？蒲许?xiàng)目(2017A-047)

張明軍(1973年生)，男；研究方向圖的標(biāo)號(hào)與復(fù)雜網(wǎng)絡(luò)；E-mail: zhangmjlz@163.com

O157.5

A

0529-6579(2017)06-0060-04

DOI:10.13471/j.cnki.acta.snus.2017.06.009