树的二分全优美标号  

Bipartite Total Graceful Labeling of Trees

作　　者：姚明[1] 黄建华[1] 姚兵[2] 

机构地区：[1]兰州石化职业技术学院,甘肃兰州730060 [2]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《兰州交通大学学报》2017年第6期132-135,共4页Journal of Lanzhou Jiaotong University

基　　金：国家自然科学基金(61163054);甘肃省高等学校研究生导师科研项目(1216-01);甘肃省财政厅专项资金(2014-63)

摘　　要：一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k?二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法.The labeling of the connected graph G with q edges is an injection f,so that each vertice of graph Gis assigned different integers.If a set of all edge labels must be equal to [1,q],fis called a graceful labeling,Gis a graceful graph.The graceful labeling can be used to solve Rosa Decomposition Conjecture,which needs to prove every tree is graceful.However,it still causes a problem.As we all known,the bipartite labeling of trees is used to product some results that can be regarded as an approximation toward the Graceful Tree Conjecture.Therefore,a conjecture which is weaker than the conjecture of the graceful tree can be considered：a bipartite total graceful Tis a tree such that the graph obtained by deleting all leaves fromTis just a caterpillar.A bipartite labeling of a tree Tis a bijection ffor which there is a positive number k,such that f（u）≤k≤f（v）,then vertice uand vbe corresponding to different bipartite sets.A k-bipartite total graceful labeling of a tree and a graceful space are defined,a class of bipartite total graceful tree is proved and some ways are presented for constructing a large scale of bipartitc total graceful trees.

关 键 词：全优美标号 全优美空间 运算关系 二分优美标号 k-二分全优美 

分 类 号：O157.5[理学—数学]