两类特殊图的邻和可区别全染色*

刘蒙蒙，红 霞

（洛阳师范学院数学科学学院，河南 洛阳 471022）

1 引言

本文中所有指定的图均为无向简单图，如文中没有进行说明的图论符号和术语同文献[1].设G＝（V，E）是一个简单图，其顶点集为V＝V（G），边集为E＝E（G）.对任意u∈V（G），NG（u）表示点u在G中的邻集，NG[u]＝NG（u）∪{u}表示点u在G中的闭邻集，dG（u）＝NG（u）表示点 u在 G 中的度，而 δ＝δ（G）和 Δ＝Δ（G）分别表示图 G 的最小度和最大度.在不致混淆情况下，可将 NG（u），NG[u]，Δ（G），δ（G）分别简单记为 N（u），N[u]，Δ，δ.

图染色问题是图论中很重要的研究课题之一.它涵盖的内容比较丰富，包括顶点染色，边染色，全染色以及延伸的多种形式的染色概念[2-4].自从张忠辅教授提出图的邻点可区别边染色和邻点可区别全染色概念之后，很多相关学者依次加入到该研究领域并展开研究.事实上，图的邻和可区别染色理论是图的邻点可区别染色的一种推广，它具有重要的意义和研究价值[5].与邻点可区别染色相比较，邻和可区别染色有更加严格的限制条件.近几年，与“和（Sum）”有关的染色问题的研究越来越活跃[6-8].2011年，Monika和Mariusz[9]首次提出图的邻和可区别全染色概念.Monika等人提出了关于图G的邻和可区别全染色的猜想：对每一个最大度为Δ的图G，有成立，并给出此猜想对完全图、圈、二分图成立.本文主要给出两类图即蜘蛛图n·Pm和圈的冠图Ir（Cm）的邻和可区别全染色数的精确值，从而说明了此猜想对这两类图是成立的.

2 基本概念

定义 1[9]设图 G 是阶数不小于 2 的连通图，[k]＝{1，2，3，…，k}，φ 是从 V（G）∪E（G）到[k]的映射，对于任意u∈V（G），令f（u）＝∑uv∈E(G)φ（uv）＋φ（u），如果φ满足：

（1）对于任意 uv∈E（G），有 φ（u）≠φ（v）≠φ（uv）；

（2）对于任意 uv，uw∈E（G），v≠w，有 φ（uv）≠φ（uw）.则称 φ 为图 G 的正常[k]-全染色.若进一步满足：

（3）对任意的uv∈E（G），有f（u）≠f（v），则称φ为图G的[k]-邻和可区别全染色，k的最小值称为图G的邻和可区别全色数，记为.

定义2具有一个公共点的n条长为m－1的路Pm组成的图，称为蜘蛛图，记为n·Pm（其中公共点是n条路的端点粘合而成的）.

定义3在一个图G的每一个顶点均增加r（r≥1）条悬挂边所得的图，称为图G的r-冠图，记为Ir（G）.1-冠图简称为冠图，记为I（G）.

引理1[9]对任意阶至少为2的简单连通图G，有，其中 Δ（G）为图G的最大度.

引理2[9]若阶至少为2的简单连通图G中存在相邻的最大度点，则

3 主要结果及证明

定理1对于蜘蛛图n·Pm（n≥3），有

证明：令图G＝n·Pm，其顶点集和边集为

故此时满足定义1，从而φ是图G的一个[n＋1]-邻和可区别全染色，所以.定理1证毕.

定理2对于冠图Ir（Cn）（r≥1，n≥3），有

证明：令G＝Ir（Cn）（r≥1，n≥3），其点集和边集为