复合树的Felicitous性质

张明军，杨思华，姚兵

(1. 兰州财经大学信息工程学院，甘肃 兰州 730020；2. 兰州财经大学陇桥学院，甘肃 兰州 730101；3. 西北师范大学数学与统计学院，甘肃 兰州 730070)

复合树的Felicitous性质

张明军1，杨思华2，姚兵3

(1. 兰州财经大学信息工程学院，甘肃 兰州 730020；2. 兰州财经大学陇桥学院，甘肃 兰州 730101；3. 西北师范大学数学与统计学院，甘肃 兰州 730070)

将多个具有集有序 Felicitous 性质的树上的点与一棵集有序优美树上的点重合，构造出一棵较大的复合树, 经研究计算, 该复合树具有集有序 Felicitous 性质。

复合树; 集有序 Felicitous 标号; 集有序优美标号

图的标号广泛应用于编码理论、通讯网络、物流、同步机码设计、无线电频道分配和读取DNA序列等领域。 优美图是图的标号研究中十分重要的课题之一。1966年, Rosa[1]提出了一个猜想：每一棵树都是优美树。后来，Bermond[2]又提出了猜想：所有龙虾树都是优美树。关于这两个猜想已经有了很多结果, 但是一直没有彻底的解决。Lee等[3]于 1991 年提出了猜想：每一棵树都是 Felicitous 树。该猜想与优美树猜想具有同等的理论价值, 而且具有相同的难度, 都是 NP-hard 问题[4-13]。对于数学猜想的进攻, 导致图的标号迅速发展成为当今图论学科中十分活跃的分支。

1 预备知识

本文涉及的图均为有限、无向简单图。文中没有定义的术语和符号均来自文献[14]。为叙述简便，我们把一个有p个顶点q条边的连通图记为(p,q)-图。记号[m,n]表示非负整数集合{m,m+1,m+2,…,n}，其中m和n均为整数，且满足0≤m

定义1 设G是(p,q)-图，若存在一个单射f:V(G)→[0,q]，使得边标号集合{f(uv)|uv∈E(G)}=[0,q-1]，其中边标号为f(uv)=f(u)+f(v)(modq)，那么称G是Felicitous图，并称f是G的一个Felicitous 标号。进一步，设(X,Y)是二部图G的顶点集的一个二部划分，如果G有一个Felicitous 标号f，使得

max{f(x)|x∈X}

(以下简记为f(X)

则称G是集有序 Felicitous 图，也称f是G的一个集有序 Felicitous 标号。

对于定义1中的图G和Felicitous标号f，以下简记顶点标号集合为f(V(G))={f(u)|u∈V(G) }，边标号集合为f(E(G))={f(u)+f(v)|uv∈E(G) }，以及f(E(G))(modq)={f(uv)|uv∈E(G) }。

定义2 设G是(p,q)-图，若存在一个单射f:V(G)→[0,q]，使得边标号集合{f(uv)|uv∈E(G) }=[1,q]，其中边标号为f(uv)=|f(u)-f(v)|，那么称G是优美图，并称f是G的一个优美标号。进一步，设(X,Y)是二部图G的顶点集的一个二部划分，若G有一个优美标号f，使得f(X)

定义3 设T,H1,H2,…,Hp是树，|V(T)|=p，V(T)={wi|i∈[1,p] }，|V(Hi)|=n，|V(Hi)|={ui,j|i∈[1,p],j∈[1,n] }，将T的顶点wi(i∈[1,p])与树Hi中的一个ui,j0(j0∈[1,n])重合，得到的图G叫做复合树，特记为G=[T;H1,H2,…Hp]。

2 主要结论及其证明

定理1 设树H1,H2,…,H|V(T)|有集有序 Felicitous 标号，树T是集有序优美树，且其顶点集二部划分(X,Y)满足||X|-|Y||≤1，则复合树[T;H1,H2,…,H|V(T)|]具有集有序 Felicitous 标号。

证明根据定理假设, 树T是有p个顶点的集有序优美树，其顶点集二部划分为(X,Y)，其中||X|-|Y||≤1，X={w1,w2,…wl}，Y={wl+1,wl+2,…wp}。树T有一个集有序优美标号f，使得f(wi)=i-1，i∈[1,p]，并且f(X)

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

利用f定义T的一个标号f′如下：f′(wi)=f(wi)+1=i，i∈[1,p]。由p的奇偶性来定义复合树[T;H1,H2,…Hp]的一个标号h。

情形Ⅰ 当p=2β+1时，从而有||X|-|Y||=1。令|X|=|Y|+1。我们定义复合树[T;H1,H2,…Hp]的标号h如下：

(i) 当k∈[1,β+1]时，令

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

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

(ii) 当l∈[β+2,2β+1]时, 令

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

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

经过计算得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*)是复合树[T;H1,H2,…Hp]的顶点集二部划分，则有h(X*)

下面，证明标号h是复合树[T;H1,H2,…Hp]的集有序Felicitous 标号。

当k∈[1,β+1]，i∈[1,s]和j∈[1,t]时，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]

当l∈[β+2,2β+1]，i∈[1,s]和j∈[1,t]时，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) 对固定的i0∈[1,s]，将Hm(m∈[1,2β+1])的顶点um,i0与树T的顶点wm重合。对k∈[1,β+1]，l∈[β+2,2β+1]，关于复合树[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

经过计算得

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

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

3nβ+s-1]=N*

2) 对固定的j0∈[1,t]，将Hm(m∈[1,2β+1])的顶点vm,j0与树T的顶点wm重合。对k∈[1,β+1]，l∈[β+2,2β+1]，计算复合树[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

经过计算得

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

综上得，边标号集合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*)

故当p是奇数时，标号h是复合树[T;H1,H2,…Hp]的集有序 Felicitous 标号。

情形Ⅱ 当p=2β时，则有||X|-|Y||=0。定义标号h如下：

(i) 当k∈[1,β]时, 令

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

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

(ii) 当l∈[β+1,2β]时, 令

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

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

用与奇数情形相同的方法, 可得到边标号集合

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

[0,2nβ-2]

综合情形 1 和情形 2 的讨论, 本定理得证。(图1与图2是解释定理1的两个例子)

图1 解释定理1的一个例子Fig.1 An example for illustrating Theorem 1

图2 解释定理1的另一个例子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类优美图的冠的优美标号[J]. 中山大学学报(自然科学版), 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] 赵喜杨, 姚兵. 探讨树的(k,d)-边魔幻全标号[J]. 中山大学学报(自然科学版), 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-树的二分强优美性和二分强奇优美性[J]. 应用数学学报, 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)的交错标号[J]. 中山大学学报(自然科学版), 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

国家自然科学基金(61363060, 61662066)；兰州财经大学高等教育教学改革研究重点项目(LJZ201707)；甘肃省高等学校科研项目(2017A-047)

张明军(1973年生)，男；研究方向图的标号与复杂网络；E-mail: zhangmjlz@163.com

O157.5

A

0529-6579(2017)06-0060-04

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