图的最大度与(p,1)-全标号

The Maximum Degree and (p,1)-Total Labeling of Graphs

图G的一个(p,1)全标号是与频道分配有关的一种染色,它是从V(G)∪E(G)到一个整数集合的映射,且满足:1)图G的任意两个相邻的顶点得到不同的整数;2)图G的任意两个相邻的边得到不同的整数;3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差p.一个(p,1)-全标号的跨度是指最大标号数与最小标号数的差.图G的所有(p,1)-全标号函数T中最小的跨度,称为图G的(p,1)-全标号数,记为λp(G).本文我们证明了对任意的图G,其最T大度△是偶的且至少是10,则λ2≤2△-1.另外对于任意的简单连通图G,其最大度为△,如T果G的最大度点的邻点中至多有△-1个最大度点,则λp(G)≤p+4.

A （p,1）-total labeling of graph G is an assignment of integers to V（G）∪E（G） such as： 1） any two adjacent vertices of G receive distinct integers; 2） any two adjacent edges of G receive distinct integers; 3） a vertex and its incident edges receive integers that differ by at least p in absolute value. The span of a （p,1）-total labeling of G is T T called the （p,1）-total number and denoted by λp （G）. In this paper we prove that λ2 ≤ 2△ 1 for any graph G T with the maximum degree △ ≥ 10 and △ is even. In addition, T we prove that λp^T （G） ≤ p ＋ 4 for any simple connected graph G provided that the number of vertices with maximum degree which is adjacent to any vertex with maximum degree of G at most △- 1.