图的半强积的邻点可区别染色

Adjacent vertex-distinguishing colorings of the semistrong product of graphs

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a^((r))(G),其中r=1,2,且X_a^((1))(G)与X_a^((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.

The semistrong product of simple graphs G and H is the simple graph G＊H with vertex set V（G） × V（H）, in which （u, v） is adjacent to （u ＇, v＇） if and only if either u = u＇ and vv＇ ∈ E（H） or uu＇ ∈ E（G） and vv＇ ∈ E（H）. An adjacent vertex distinguishing edge （total） coloring of a graph is a proper edge （total） coloring of the graph such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex distinguishing edge coloring and adjacent vertex distinguishing total coloring of a graph are collectively called the adjacent vertex distinguishing coloring of the graph. The minimum number of colors required for an adjacent vertex distinguishing coloring of G is called the adjacent vertex distinguishing chromatic number of G, and denoted by Xa（t）（G）, where T= 1, 2, Xa（1） （G） and Xa（2） （G） denote the adjacent vertex distinguishing edge chromatic number and adjacent vertex distinguishing total chromatic number, respectively. An upper bound for these parameters of the semistrong product of two simple graphs G and H is given in this paper, and it is proved that the upper bound is attained precisely. Then the necessary and sufficient conditions is discussed which the two different semistrong product of two trees have the same the value of these parameters. Furthermore, the exact value of these parameters for the semistrong product of a class graphs and complete graphs are determined.