Header menu link for other important links
On Coupon Coloring of Cartesian Product of Some Graphs
Published in Springer Science and Business Media Deutschland GmbH
Volume: 12601 LNCS
Pages: 309 - 316
Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of k colors to the vertices of G such that every vertex contains vertices of all k colors in its neighborhood. The coupon chromatic number of G, denoted χc(G), is the maximum k for which a k-coupon coloring exists. In this paper, we present an upper bound for the coupon chromatic number of Cartesian product of graphs G and H in terms of |V(G)| and |V(H)|. Further, we prove that if G and H are bipartite graphs then G□ H has a coupon coloring with 2 min { χc(G), χc(H) } colors. As consequences, for any positive integer n, we obtain the coupon chromatic number and total domination number of n-dimensional torus □i=1nCki with some suitable conditions to each ki, which turns out to be a generalization of the result due to S. Gravier [Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119–128]. Finally, for any r≥ 0, d≥ 2, we obtain the coupon coloring for the Hamming graph Kd□ Kd□ ⋯ □ Kd (2r times). © 2021, Springer Nature Switzerland AG.