树的二分全优美标号

Bipartite Total Graceful Labeling of Trees

一个有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.