幂图的邻点可区别全色数

Adjacent vertex distinguishing total chromatic number of power graph

在一个简单图的基础上,连接任两个最短路长为k的两个顶点,得到原图的k幂。根据幂图的结构性质,利用穷染,递推,换色的方法,对树的k幂和圈的2幂的进行邻点可区别全染色,并得到了邻点可区别全色数。特别的,在存在两个相邻最大度点时,按k的3剩余类进行分类,在k≠3a,a为偶数的情况下,树的k幂的邻点可区别全色数为6.

Based on a simple graph, if every couple of nodes which the minimal path length between them is k are connected,a k power graph is obtained. According to the properties of power graphs, using coloring one by one, recursion, changing colors, the k power graph of trees and the 2 power graph of cycles are colored by the adjacent vertex distinguishing total coloring, and the adjacent vertex distinguishing total chromatic number is determined. Especially, when the graph has two neighbor maximal degree nodes, and the power graphs of paths are classified by k/3. The k（k≠3a, a is even） power graphs of trees＇ adjacent vertex distinguishing total chromatic number is 6.