Operations Research Transactions
Previous Articles
TIAN Shuangliang1,* DONG Xinfang1 LIU Ruilin1
Received:
Online:
Published:
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
TIAN Shuangliang, DONG Xinfang, LIU Ruilin. Adjacent vertex-distinguishing colorings of the semistrong product of graphs[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.03.013.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.03.013
https://www.ort.shu.edu.cn/EN/Y2017/V21/I3/119