一类图空间的集有序强优美性

一类图空间的集有序强优美性 On Set-Ordered Strong Gracefulness of a Graphs Space first-author 马 飞，男，硕士生，主要研究方向为图的标号及染色. E-mail：mafei123987@163.com 马 飞，男，硕士生，主要研究方向为图的标号及染色. E-mail： mafei123987@163.com mafei123987@163.com corresp E-mail:yybb918@163. com E-mail:yybb918@163. com 西北师范大学 数学与统计学院，甘肃 兰州 730070 西北师范大学 数学与统计学院，甘肃 兰州 730070 College of Mathematics and Statistics，Northwest Normal University，Lanzhou 730070，Gansu, China College of Mathematics and Statistics，Northwest Normal University，Lanzhou 730070，Gansu, China 讨论了树的集有序强优美性，给出了集有序强优美树的概念，证明了由n棵集有序强优美树的任意排列构成的线性图空间仍具有集有序强优美性；给出了运用两棵同构的强优美树构造集有序强优美树的一种新方法，证明了强优美树与集有序强优美树可以构造强优美树． For studying set-ordered strong gracefulness of trees, we first define the set-ordered strong gracefulness of trees，and then show that the linear graph space constructed by any range of n set-ordered strong graceful trees has the set-ordered strong gracefulness. Secondly, we provide a method by which a set-ordered strongly graceful tree can be constructed any pair of isomorphic strongly graceful trees. At the end of this article the question of whether any strongly graceful tree can be constructed by two or more strongly graceful trees is raised. 强优美标号 集有序强优美标号 完美匹配 strongly graceful labeling set-ordered strongly graceful labeling perfect matching 引 言 1 在当今图论学科中，图的标号是相当活跃的一个分支，这是因为它有很广泛的应用，诸如：编码理论、雷达、通讯网络、射电天文学等方面 [ 1 1 ~ 4 4 1~4 ] ．文献 [ 5 5 ] 给出了著名的优美树猜想：每一棵树都有一个优美标号．如果这个猜想被解决，人们就可以解决著名的Ringel-Kotzig分解猜想：对预先给定的一棵 n +1个顶点的树 T ,每一个2 n +1个顶点的完全图K 2 n +1 都可被分解成2 n +1个同构于树 T 的子图．到目前为止，优美树猜想仍然没有被完全解决，这使得优美树猜想至今仍然是一个吸引人解决的问题，由于不断地对这个猜想进行研究、实验、进攻，导致了各种图的标号与着色技术迅速发展 [ 6 6 ~ 8 8 6~8 ] ．本文论及的图均为简单、无向图．为了便于叙述，引入记号［1, m ］( m ≥1)表示由1与 m 之间的自然数构成的集合，未说明的相关术语和符号均采用于文献 [ 9 9 ] ． 定义1 设 G 是有 n 个顶点的简单图，如果存在映射 f : V(G) →{0,1,…,| E ( G )|}，使对不同的顶点 x,y ∈ V(G) ，满足 f(x) ≠ f(y) ， G 的每一条边 uv 的标号定义为 f(uv) =| f(u) － f(v) |，且 G 的边标号互不相同，则称 G 是优美图， f 是 G 的一个优美标号． 定义2 如果一棵具有 n 个顶点且有完美匹配 M 的树 T 有一个优美标号 f ，使对每条边 uv ∈ M ,总有 f(u) + f(v) = n －1，则称 T 是强优美树， f 是 T 的一个强优美标号．设 T 的顶点二部划分为( X,Y )，若对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，则称 T 是集有序强优美树， f 是 T 的一个集有序强优美标号． 定义3 设 G 是有 p 个顶点 q 条边的(p,q)-图，如果存在一个映射 f : V ( G )→［0, k +( q －1) d ］，使得边标号集合 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464964&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464964&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464964&type=middle 称 f 是图 G 的一个( k,d )-优美标号．如果 G 有完美匹配M和一个( k,d )-优美标号 f ，使得对每条边 uv ∈ M ,总有 f(u) + f(v) = k +( q －1) d ，则称 G 是( k,d )-强优美图， f 是 G 的一个( k,d )-强优美标号．若 G 是具有顶点二部划分( X,Y )的二分图，且对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，则称 G 是集有序( k,d )-强优美图， f 是 G 的一个集有序( k,d )-强优美标号． 在本文的研究中需用到一个原则，即：将一棵强优美树 T 的顶点集合 V ( T )在属于它的任意强优美标号 f 下划分为两个集合 V ( X )与 V ( Y )， T =( X,Y )，对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，称这种划分为顶点标号二部划分原则．我们先将下文中将要用到的记号做一说明， H =〈 T i 1 , T i 2 ,…, T in 〉表示 T i 1 ⊕ T i 2 ⊕…⊕ T in ，其中 T i 1 ⊕ T i 2 表示在顶点 x i 1 max与顶点 y i 2 max之间用一条边连接所形成的树(f是 T i 1 的一个集有序强优美标号， T i 1 =( X i1 ,Y i1 )， x i 1 max∈ X i 1 ，对任意的 u ∈ X i1且 u ≠ x i 1 max，有 f(u) < f ( x i 1 max)； g 是 T i 2 的一个集有序强优美标号， T i 2 =( X i 2 , Y i 2 )， y i 2 max∈ Y i2，对任意的 v ∈ Y i 2 且 v ≠ y i 2 max，有 f(v) < f ( y i 2 max))．由于1,2,…, n 这 n 个数的全排列数为 n !，那么我们就可以用这 n 个集有序强优美树 T 1 , T 2 ,…, T n 做成基，生成 n !个树(包括同构)．形象地看是将一条长为 n 的路通过将每个顶点 x j 换成树 T ij 扩展成一个庞大的复杂的树，因此称这 n !个树构成了一个线性图空间． 定理及其证明 1 定理1 n 个集有序强优美树 T 1 , T 2 ,…, T n 构成的线性图空间中每一棵树均为集有序强优美树． 由于在这个线性图空间中每一棵树的任意性及树的个数 n 的任意性使得定理1的证明比较复杂，为此我们先看一个特殊情形，如下： 定理2 T , T ′是两个二分强优美树，那么树 H =〈 T , T ′〉也是二分强优美树． 证 针对树 T 与树 T ′的阶数与结构差异性，证明分三类. 第一类：若 T , T ′是两个同构的强优美树(见例1)，且| V ( T )|=| V ( T ′)|=2 n ，给强优美树 T 一个强优美标号f及完美匹配 R 1 ，使得 T =( X,Y )，对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，边 uv ∈ R 1 ，都有 f(u) + f(v) =2 n －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465085&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465085&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465085&type=middle ；给二分强优美树 T ′一个二分强优美标号 f ′及完美匹配 R 2 ，使得 T ′=( X ′, Y ′)，对任意的 x ′∈ X ′, y ′∈ Y ′,都有 f ′( x ′) < f ′( y ′)，不妨记作 f ′( X ′) < f ′( Y ′)，边 u ′ v ′∈ R 2 ，都有 f ′( u ′)+ f ′( v ′)=2 n －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464966&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464966&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464966&type=middle 对任意的 u ∈ V ( T )，存在 u ′∈ V ( T ′)，使得 f(u) = f ′( u ′)，在 u 与 u ′间连一条边，得到的树记为树 H =〈 T , T ′〉，下证树H是二分强优美的．依二分强优美标号f与 f ′给树 H =〈 T , T ′〉=( X ∪ Y ′, Y ∪ X ′)=( M,N )定义一个新的标号 g ： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464972&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464972&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464972&type=middle 显然，对任意的 x ∈ M , y ∈ N ,都有 f(x) < f(y) ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465089&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465089&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465089&type=middle ,顶点标号集合 g ( V(H) )=［0,4 n －1］．在树H中子树 T 的边标号集合 G 1 满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464976&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464976&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464976&type=middle 在树 H 中子树 T ′的边标号集合 G 2 满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464978&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464978&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464978&type=middle 边 uu ′的标号 g(uu′) =| g(u′)－g(u) |=2 n ，则得树 H 的边标号集合 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464981&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464981&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464981&type=middle 任意的边 uv ∈ R ( R = R 1 ∪ R 2 为树H的完美匹配)满足 g(u) + g(v) =4 n －1．从而，树H是二分强优美树， g 是树 H 的一个二分强优美标号． 第二类：若 T , T ′是两个不同构的二分强优美树，但| V ( T )|=| V ( T ′)|=2 n ，证明方法与第一类的类似． 第三类：若 T , T ′是两个二分强优美树且| V ( T )|≠| V ( T ′)|(见例2)，不妨设2 n =| V ( T )| > 2 m =| V ( T ′)|，给二分强优美树 T 一个二分强优美标号 f 及完美匹配 R 1 ，使得 T =( X,Y )，对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，边 uv ∈ R 1 ，都有 f(u) + f(v) =2 n －1且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465094&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465094&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465094&type=middle ；给二分强优美树 T ′一个二分强优美标号 f ′及完美匹配 R 2 ，使得 T ′=( X ′, Y ′)，对任意的 x ′∈ X ′, y ′∈ Y ′,都有 f ′( x ′) < f ′( y ′)，不妨记作 f ′( X ′) f ′( Y ′)，边 u ′ v ′∈ R 2 ，都有 f ′( u ′)+ f ′( v ′)=2 m －1且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465100&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465100&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465100&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465105&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465105&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465105&type=middle . 1) 当 n ≥2 m 时，对任意的 u ′∈ Y ′，存在 v ∈ X ，使得 f(v) － f ′( u ′)= n －2 m ，或者对任意的 u ′∈ X ′，存在 v ∈ Y ,使得 f(v) － f ′( u ′)= n ，在顶点 v 与顶点 u ′间连一条边，得到的树记为 H 1 =〈 T , T ′〉； 2) 当 m < n < 2 m 时，对任意的 u ′∈ Y ′，存在 v ∈ X ，使得 f ′( u ′)－ f(v) =2 m － n ，或者对任意的 u ′∈ X ′，存在 v ∈ Y ,使得 f(v) － f ′( u ′)= n ，在顶点 v 与顶点 u ′间连一条边，得到的树记为 H 2 =〈 T , T ′〉． 下证树 H 1 与树 H 2 是集有序强优美的，仅证树 H 1 是集有序强优美的，这是因为树 H 2 的证明与树 H 1 的证明相同．依集有序强优美标号f与 f ′，给树 H 1 =〈 T , T ′〉=( X ∪ Y ′, Y ∪ X ′)=( M,N )定义一个新的标号 g 为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464985&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464985&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464985&type=middle 显然，对任意的 x ∈ M , y ∈ N ,都有 f(x) < f(y) ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465108&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465108&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465108&type=middle ,顶点集合 g(V(H)) =［0,2( n + m )－1］．在树 H 1 中，子树 T 的边标号集合 G 1 为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464989&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464989&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464989&type=middle 在树 H 1 中，子树 T ′的边标号集合 G 2 为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464991&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464991&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464991&type=middle 边 uu ′的标号 g ( u u ′)=|g( u ′)－ g(u) |=2 m ，可算出树 H 1 的边标号集合为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464999&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464999&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464999&type=middle 且对任意的边 uv ∈ R ( R = R 1 ∪ R 2 为树 H 的完美匹配),都有 g(u) + g(v) =2( n + m )－1，从而树 H 1 是集有序强优美的， g 是树 H 1 的一个集有序强优美标号．至此，定理2证毕． 例1 集有序强优美树 T 与同构的集有序强优美树 T ′产生新的集有序强优美树(如 图 1 图 1 )． 注： 红色点构成小标号集合,方框中的数字代表新产生的边标号 The red vertices stand for the smaller set,the number of rectangle is new edge labelling 例2 二分强优美树 T 与二分强优美树 T 1 产生新的二分强优美树(如 图 2 图 2 )． 再证定理1，对 n 个集有序强优美树 T 1 , T 2 ,…, T n 的任意一个有序排列 T i 1 , T i 2 ,…, T in ，可以两两组合采用定理2证明中的构造法产生新的集有序强优美树，以此类推便可构造出一族树 T ={〈 T i 1 , T i 2 ,…, T in 〉| i 1, i 2,…, in 是1,2,…, n 的一个有序排列}，显然， T 中的每个树都是二分强优美树．这样我们可以看到定理1中的线性图空间仅是树族 T 的一个类． 推论1 T , T ′是两个二分强优美树，那么树 H =〈 T , T ′〉是二分( k,d )-强优美树． 证 依据定理2中树 H=（M,N） 的标号 g 作一个新的标号 τ ：对任意的 u ∈ M ，有 τ（u） =g（u）d ；对任意的 v ∈ N ，有 τ（v） = k + （g（v） －1） d ．显然，顶点标号集合 τ （ V（H） ）=［0, k +（| E（H) |－1） d ］，边标号集合 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465014&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465014&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465014&type=middle 且任意的边 uv ∈ R ( R = R 1 ∪ R 2 为树 H 的完美匹配)，都有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465017&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465017&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465017&type=middle 则标号 τ 是树 H 的一个( k,d )-强优美标号，树 H 是( k,d )-强优美树．根据构造法易知在 H =〈 T , T ′〉=( X ∪ Y ′, Y ∪ X ′)=( M,N )中对任意的 x ∈ M , y ∈ N ,都有 f(x) < f(y) ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465113&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465113&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465113&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465118&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465118&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465118&type=middle ，那么标号 τ 就是树 H 的一个集有序( k,d )-强优美标号，树 H 就是集有序( k,d )-强优美树． 在推论1中，当 k =1, d =1时，标号 τ 就是集有序强优美标号；当 k =1, d =2时，标号 τ 就是集有序强奇优美标号．定理1给了我们一种用若干个小的集有序强优美树构造出大的集有序强优美树的方法，用此方法我们证明了一族树的集有序强优美性，是否能将条件弱化产生新的结论呢？通过实验可以作出一些改进，便有如下定理3． 定理3 T 1 , T ′ 1 , T 2 , T ′ 2 ,…, T n , T ′ n 是2 n 个强优美树且 T i 与 T ′ i ( i ∈［1, n ］)同构， H i =〈 T 1 , T ′ 1 〉,则对任意的一个排列 H i1 , H i2 ,…, H in ，树 H =〈 H i1 , H i2 ,…, H in 〉是强优美树． 由于树 T 的任意性及树的个数 n 的任意性使得定理3的证明更加复杂，为顺利完成定理3的证明，我们先证明一个特殊情形，如下： 定理 4 T , T ′是两个同构的强优美树，那么树 H =〈 T , T ′〉是强优美树． 证 T , T ′是两个同构的强优美树且| V ( T )|=| V ( T ′)|=2 n ，依顶点标号二部划分原则给强优美树 T 一个强优美标号 f 及完美匹配 R 1 ，使得 T =( X,Y )，对任意的 x ∈ X , y ∈ Y ,都有 f(x) < f(y) ，不妨记作 f(X) < f(Y) ，边 uv ∈ R 1 ，都有 f(u) + f(v) =2 n －1，同理给强优美树 T ′一个强优美标号 f ′及完美匹配 R 2 ，对任意的 x ′∈ X ′, y ′∈ Y ′,都有 f ′( x ′) < f ′( y ′)，不妨记作 f ′( X ′) < f ′( Y ′)，边 u ′ v ′∈ R 2 ，都有 f ′( u ′)+ f ′( v ′)=2 m －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465122&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465122&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465122&type=middle ．对任意的 x ∈ V ( T )，存在 x ′∈ V ( T ′)，使得 f(x) = f ′( x ′)，在 x 与 x ′间连一条边，得到的树记为树 H =〈 T , T ′〉．依强优美标号 f 与 f ′给树 H =〈 T , T ′〉=( X ∪ Y ′, Y ∪ X ′)=( M,N ) 定义一个新的标号 g ： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465021&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465021&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465021&type=middle 显然，对任意的 x ∈ M , y ∈ N ,都有 f(x) < f(y) ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465125&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465125&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465125&type=middle ,顶点标号集合 g(V(H)) =［0,4 n －1］．在子树 T 中依点标号为0的顶点为初始点做二部划分，在子树 T ′中依点标号为2 n －1的顶点为初始点做二部划分， T =( X * , Y * )，存在 s ∈ X * ，使 g(s) =0； T ′=( X ′ * , Y ′ * )，存在 s ′∈ X * ，使 g ( s ′)=2 n －1．将不符合二部划分原则的同构点的标号互换( T : u ∈ X * , v ∈ Y * , α = g(u)>g(v) = β 且 g(u)+g(v) =4 n －1； T ′: u ′∈ X ′ * , v ′∈ Y ′ * , λ = g ( u ′) > g ( v ′)= γ ,且g( u ′)+g( v ′)=4 n －1； g(u) = λ ， g (v) = γ ， g ( u ′)= α ， g ( v ′)= β ).至此,标号完成. 下证树 H 是强优美的．标号过程中我们会发现这样一个现象，在发生同构点的标号互换之后，树 H 的边标号仅仅改变的是连接初始互换标号顶点(如连接顶点 u , u ′)边的边标号，这些边标号作成的集合记 G 1 ： G 1 = G ′ 1 ∪ G ″ 1 (其中 G ′ 1 表示原来在子树 T 上的点标号互换给子树 T ′上的同构点后边标号产生改变的集合， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465026&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465026&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465026&type=middle ( u 是初始互换标号的顶点， w 是未互换标号的顶点) G ″ 1 表示原来在子树 T ′上的点标号互换到子树 T 上的同构点后边标号产生改变的集合， G ″ 1 ={ g(uw) | g(uw) =2 n +( u′w′ ), u′,w′ ∈ V ( T ′), u ′ v ′∈E( T ′); u,w ∈ V ( T ), uv ′∈ E ( T )}( u ′是初始互换标号的顶点， w ′是未互换标号的顶点))．未发生同构点的标号互换之前树H中子树 T 的边标号集合 G 2 = G ′ 2 ∪ G ″ 2 ,其中， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465034&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465034&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465034&type=middle 树 H 中子树 T ′的边标号集合 G 3 = G ′ 3 ∪ G ″ 3 ,其中， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465041&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465041&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465041&type=middle 边 xx ′的标号g(x x ′)=|g( x ′)－ g(x) |=2 n ，那么最终树 H 的边标号集合 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465048&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465048&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465048&type=middle 显然,对任意的 x ∈ M , y ∈ N ,都有 f(x) < f（y） ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465128&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465128&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465128&type=middle , 顶点标号集合 g（V（H）） =[0,4 n －1]，从而树 H 是强优美树， g 是树 H 的一个强优美标号． 至此，定理4证毕． 再述定理3，对于 T 1 , T ′ 1 , T 2 , T ′ 2 ,…, T n , T ′ n 这2 n 个强优美树，先将 T i 与 T ′ i 采用定理4证明中的构造法构造产生新的强优美树 H i ，然后两两组合，以此类推便可构造出强优美树H=〈 H i1 , H i2 ,…, H in 〉． 推论2 T是个二分强优美树， T ′是个强优美树，| V（T） |≥|V（ T ′）|，那么树 H =〈 T,T ′〉是强优美树． 证 由于 T 是二分强优美树， T ′是强优美树，且有2 n =| V（T） |≥|V（ T ′）|=2 m ，则二分强优美树 T 有一个二分强优美标号 f ，使得 T =（ X,Y ），对任意的 x ∈ X , y ∈ Y , 都有 f（x） < f（y） ，不妨记作 f（X） < f（Y） ，边 uv ∈ R 1 ，都有 f（u） + f（v） =2 n －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465131&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465131&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465131&type=middle ；依顶点标号二部划分原则给强优美树 T ′一个强优美标号 f ′，使 T ′=（ X ′, Y ′），对任意的 x ′∈ X ′, y ′∈ Y ′, 都有 f ′（ x ′） < f ′（ y ′），不妨记作 f ′（ X ′） < f ′（ Y ′），边 u ′ v ′∈ R 2 ，都有 f ′（ u ′）+ f ′（ v ′）=2 m －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465134&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465134&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465134&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465136&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465136&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465136&type=middle ． 1） 若 n ≥2 m ，任意的 u ′∈ Y ′，存在 v ∈ X ，使得 f（v） － f ′（ u ′）= n －2 m 或任意的 u ′∈ X ′，存在 v ∈ Y , 使得 f（v） － f ′（ u ′）= n ，在顶点 v 与顶点 u ′间连一条边，得到的树记为树 H 1 =〈 T , T ′〉； 2） 若 m ≤ n < 2 m ，任意的 u ′∈ Y ′，存在 v ∈ X ，使得 f ′（ u ′）－ f（v） =2 m － n 或任意的 u ′∈ X ′，存在 v ∈ Y , 使得 f（v） － f ′（ u ′）=n，在顶点v与顶点 u ′间连一条边，得到的树记为树 H 2 =〈T, T ′〉． 下证树 H 1 是强优美的，树 H 2 是强优美的证明类似．依强优美标号 f 与 f ′给树 H 1 =〈 T , T ′〉=（ X ∪ Y ′, Y ∪ X ′）=（ M,N ）定义一个新的标号 g ： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465053&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465053&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465053&type=middle 显然，对任意的 x ∈M， y ∈ N , 都有 f（x） < f（y） ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465139&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465139&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465139&type=middle , 顶点标号集合 g（V（H）） =[0,2（ n + m ）－1]．在树 H 1 中子树 T 的边标号集合： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465058&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465058&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465058&type=middle 在树 H 中子树 T ′的边标号集合： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465066&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465066&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465066&type=middle 边 vu ′的标号 g （ vu ′）=| g （ u ′）－ g（v） |=2 m ，既而树 H 1 的边标号集合 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465144&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465144&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465144&type=middle , 从而树 H 1 是强优美树， g 是树 H 1 的一个强优美标号．至此，推论3证毕． 推论3 T 是个二分强优美树， T ′是个强优美树，| V（T） |≤| V （ T ′）|，那么树 H =〈 T , T ′〉是强优美树． 证 T 是个二分强优美树， T ′是个强优美树，不妨设2 n =| V（T） |≤| V （ T ′）|=2 m , 给二分强优美树T一个二分强优美标号 f ，使得 T =（X,Y），对任意的 x ∈ X , y ∈ Y , 都有 f （ x ） < f（y） ，不妨记作 f（X） < f（Y） ，边 uv ∈ R 1 ，都有 f（u） + f（v） =2 n －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465147&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465147&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465147&type=middle ；依顶点标号二部划分原则给强优美树 T ′一个强优美标号 f ′，使得 T ′=（ X ′, Y ′），对任意的 x ′∈ X ′, y ′∈ Y ′, 都有 f ′（ x ′） < f ′（ y ′）. 不妨记作 f ′（ X ′） < f ′（ Y ′），边 u ′ v ′∈ R 2 ，都有 f ′（ u ′）+ f ′（ v ′）=2 m －1，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465149&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465149&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465149&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465152&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465152&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465152&type=middle ． 1） 当 m ≥2 n 时，任意的 u ′∈ Y ′，存在 v ∈ X ，使得 f（v） － f ′（ u ′）= n －2 m 或任意的 u ′∈ X ′，存在 v ∈ Y , 使得 f（v） － f ′（ u ′）= n ，在顶点 v 与顶点 u ′间连一条边，得到的树记为树 H 1 =〈T, T ′〉； 2） 当 n < m < 2 n 时，任意的 v ∈ X ，存在 u ′∈ Y ′，使得 f ′（ u ′）－ f（v） =2 m － n 或任意的 v ∈ Y ，存在 u ′∈ X ′, 使得 f（v） － f ′（ u ′）= n ，在顶点 v 与顶点 u ′间连一条边，得到的树记为树 H 2 =〈 T , T ′〉． 下证树 H 1 是强优美的，树 H 2 是强优美的证明类似．依强优美标号f与 f ′给树 H 1 =〈T, T ′〉=（ ∪ Y ′,∪ X ′）=（ M,N ）定义一个新的标号： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465071&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465071&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465071&type=middle 显然，对任意的 x ∈ M , y ∈ N , 都有 f（x） < f（y） ，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465157&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465157&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465157&type=middle , 顶点集合 g（V（H）） =[0,2（ n + m ）－1]．在树 H 1 中子树 T 的边标号集合： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465078&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465078&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465078&type=middle 在树 H 1 中子树 T ′的边标号集合： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465082&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465082&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465082&type=middle 边 vu ′的标号 g （ vu ′）=| g （ u ′）－ g（v） |=2 m ，既而树 H 1 的边标号集合 G = G 1 ∪ G 2 ∪{ g （ u u ′)}=[1,2（ n + m ）－1], 推出树 H 1 是强优美树，g是树 H 1 的一个强优美标号．至此，推论3证毕． 推论2和3说明给出一种用二分强优美树与强优美树构造产生新的强优美树的方法，能否再将此条件弱化呢？便有如下的问题． 问题 两个强优美树 T 1 , T 2 可以产生新的强优美树． 本文主要研究了一类图空间的集有序强优美性，在研究中创造性地提出一些独特的构造证明方法，这对以后进攻新的问题 [ 10 10 ~ 12 12 10~12 ] 有较大的帮助，同时也发现了新的问题，为以后深入地研究指明了方向． 参考文献 BROERSMA H J, HOEDE C. Another equivalent of the graceful tree conjecture[J]. Ars Combinatoria , 1999, 51: 183-192. GALLIAN J A. A Dynamic Survey of Graph Labeling [DB/OL].[2015-06-07] . http://web.thu.edu.tw/wang/www/Gallian_Survey.pdf http://web.thu.edu.tw/wang/www/Gallian_Survey.pdf . PEREIRA J, SINGH T, ARUMGAM S, et al. On (k, d)-skolem graceful graphs[J]. Electronic Note in Discrete Mathematics, 2015, 48: 81-88. GRAF A. A new graceful labeling for pendant graphs[J]. Aequat Math, 2014, 87: 135-145. ROSA A. On Certain Valuations of the Vertices of a Graph [DB/OL].[2015-07-07] . https://www.researchgate.net/publication/244474213_On_certain_valuations_of_the_vertices_of_a_graph_Theory_of_Graphs https://www.researchgate.net/publication/244474213_On_certain_valuations_of_the_vertices_of_a_graph_Theory_of_Graphs . 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. 周向前,姚兵,程辉. 关于0-可旋转树[J]. 华南师范大学学报(自然科学版),2011, 43(4): 54-57. ZHOU X Q, YAO B, CHEN H. On 0 rotatable trees[J]. Journal of South China Normal University (Natural Science Edition), 2011, 43( 4): 54-57(Ch). YAO B, CHENG H, YAO M, et al. A Note on Strongly Graceful Trees[J]. Ars Combinatoria, 2009, 92: 155-169. BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: The MaCmillan Press ltd , 1976. ZHOU X Q, YAO B, CHEN X E, et al. Every lobster is odd-elegant[J]. Information Processing Letters, 2013, 133(4): 30-33. BOXWALA S A, VASHISHTA P. Some new families of graceful graphs[J]. Electronic Note in Discrete Mathematics, 2015, 48:127-133. SUBBIAH S P, PANDIMADEVI J, CHITHRA R, et al. Super total graceful graphs[J]. Electronic Note in Discrete Mathematics, 2015, 48: 301-304. 10.14188/j.1671-8836.2016.05.011 O 157.5 whdxxblxb-52-5-471 国家自然科学基金资助项目 ( 61163054, 61363060, 61163037) 2015-04-02 2016-10-24 2020-12-10 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University（Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 5 52