姚 明,赵振学,姚 兵

(1.兰州石化职业技术学院,甘肃兰州 730060;2.西北师范大学数学与信息科学学院,甘肃兰州 730070)

关于树(图)的单点空间

姚 明1,赵振学1,姚 兵2

(1.兰州石化职业技术学院,甘肃兰州 730060;2.西北师范大学数学与信息科学学院,甘肃兰州 730070)

定义了全魔幻空间及优美空间、奇优美空间、单点空间,在空间中给出了互化标号的数学关系式,证明了标号互化可算法化,得到简练的运算过程和标号互化结果。

单点空间;奇优美空间;优美空间;全魔幻空间;运算关系

Golomb[1]提出以最小整点数刻划K个单位长的金属棒问题,这个问题在图论中可以用图的标号来描述。一个图G＝(V,E)的优美标号是对图G的顶点分配(0,1,2,…,|E|}中的数,使得不同的顶点有不同的标号,边的标号是其2个关联顶点标号差的绝对值,使得边的标号集为(1,2,…,|E|}。Rosa猜想:所有的树都是优美树,猜想如果被证明,则Ringel-Kotzig猜想成立[2-4]。

1 预备知识

1970年,Rosa定义了图G的魔幻全标号(magical total labelings,以下记为mt):对于不为零的整数s,t和一一映射f:V(G)∪E(G)→[1,p＋q],有f(x)＋f(y)＝s＋tf(xy),称f为图G的魔幻全标号[5,6]。一些新的图标号和猜想己经引起研究者的关注[7,8]。如图G的k-魔幻标号[9,10];树的二分优美(bipartite graceful,以下记为b-g);二分奇优美(bipartite odd-graceful,以下记为b-odd)[11,12]。对于图G的一个映射f:V(G)→[0,2p－3],如果有{f(uv)|uv∈E(G)}＝[1,3,…,2p－3],则称f为奇优美标号[13,14];如果图G的一个映射f:V(G)→[0,q],使得{f(uv)|uv∈E(G)}＝[1,q],称f为优美标号。设N为整数,T是一棵n个顶点的二部分图:即V(T)＝V1∪V2,V1∩V2＝∅;V1＝{xi|i∈[1,s],s∈N}与V2＝{yj|j∈[1,t],t∈N}均为独立集。相应地,图T的拷贝T∗的顶点集二部分划分为和用一条边连接顶点u∈V(T)与顶点v∈V(T∗)后所得到的图记为H。如果图T的一个标号f对所有的u∈V1和v∈V2,总有f(u)＜f(v),则称f是图T的二分标号。……