特殊图的最优标号  

Optimal Labeling on Some Special Graphs

作　　者：赵小玲[1,2] 陈广前[2] 吕长虹[2] 

机构地区：[1]上海电机学院数理部,上海200093 [2]华东师范大学数学系,上海200062

出　　处：《科技通报》2012年第2期1-3,共3页Bulletin of Science and Technology

基　　金：国家自然科学基金(No.1030010);上海市科学技术委员会项目(No.04JC14031)

摘　　要：标号图(G,L)由图G和它的标号L:V(G)→{1,2,…,n}组成。其中n=|V(G)|。在标号图(G,L)中,如果一条路P=u1,u2,…,uk(k>1)的长度为0(k=1)或者对任意的i(i=1,2,…,k-1;k>1),满足L(ui)+2>L(ui+1),则称P为不连续增长路。标号(G,L)图中所有的不连续增长路的数目记为d(G,L)。如果图G的一种标号L使得d(G,L)达到最大,则称之为图G的最优标号。在这里,给出了毛毛虫图的一种最优标号。A labeled graph is an ordered pair （G,L） consisting of a graph G and its labeling L：V（G）→[1,2, …,n],where n=IV（G）I. An increasing nonconsecutove path in a labeled graph （G,L） is either a path P=ul,u2,…,uk（k≥l） such that L（ui） ＋2≥L（u_i＋1） i（i=l,2,... ,k-1;k〉l） or k=l.The total number of increasing nonconsecutove paths in （G,L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d （G,L）.In this paper, we give an optimal labeling on caterpillars.

关 键 词：标号图 最优标号 毛毛虫图 

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