关键词: 半强积, 树, 完全图, 邻点可区别染色, 邻点可区别染色数

Abstract:

The semistrong product of simple graphs G and H is the simple graph G\bullet H with vertex set V(G)\times V(H), in which (u,v) is adjacent to (u',v') if and only if either u=u' and vv'\in E(H) or uu'\in E(G) and vv'\in 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 \chi^{(\tau)}_{a}(G), where \tau=1,2, \chi^{(1)}_{a}(G) and \chi^{(2)}_{a}(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.

Key words: semistrong product, tree, complete graph, adjacent vertex-distinguishing coloring, adjacent vertex-distinguishing chromatic number