几类特殊图的（2，1）－全标号

刘秀丽

（菏泽学院 数学系，山东 菏泽274015）

几类特殊图的（2，1）－全标号

刘秀丽

（菏泽学院 数学系，山东 菏泽274015）

研究了与频道分配有关的1种 （p，1）－全标号染色问题.（p，1）－全标号是从V（G）∪E（G）到集合｛0，1，…，k｝的1个映射，满足：①G的任2个相邻的顶点得到不同的整数；②G的任2个相邻的边得到不同的整数；③任1个点和与它相关联的边得到的整数至少相差p.通过在2个简单图之间叠加一系列匹配构造了几类有趣图，并根据所构造图的特征，利用穷染法得到了这些图的（2，1）－全标号数.

染色；（p，1）－全标号；（p，1）－全标号数；弱联图

0 引言

由于图的染色问题在现实中有着广泛应用，因而该问题受到众多学者的重视.近年来，研究者［1－3］又提出了许多新的染色问题，且这些染色问题在频率分配中得到了很好的应用，如泛宽度染色和L（p，1）－标号.特别地，Whittlesey等人在文献［4］中研究了G的剖分图的L（2，1）－标号，G的剖分图S1（G）是由图G在每条边上插入1个点所得到的图.S1（G）的L（p，1）－标号对应于G的（p，1）－全标号.

图G为简单的连通图，用V（G）和E（G）分别表示图G的顶点集和边集，对∀v∈V（G），用dG（v）表示顶点v在图G中的度，用Δ（G）表示图G中顶点的最大度.本文所讨论的图均为简单有限图.

定义1［5］设p是1个非负整数，图G的1个k－（p，1）－全标号是1个映射f∶V（G）∪E（G）→｛0，1，…，k｝，使得：①G的任2个相邻的顶点u和v，有②G的任2条相邻的边e和e′，有；③G的任2个相关联的点v和边e，有－全标号的跨度是指2个标号差的最大值，图G的（p，1）－全标号的最小跨度称为（p，1）－全标号数，记作λTp（G）.

当p＝1时，图G的（p，1）－全标号对应于图G的全染色，因此图的（p，1）－全标号也是对图的全染色的一种推广.本文主要讨论几类特……