# A Comparison on the Bounds of Chromatic Preserving Number and Dom-Chromatic Number of Cartesian Product and Kronecker Product of Paths

### Abstract

Let G be a simple graph with vertex set V and edge set E. A Set S Í V is said to be a chromatic preserving set or a cp-set if χ(<S>) = χ(G) and the minimum cardinality of a cp-set in G is called the chromatic preserving number or cp-number of G and is denoted by cpn(G). A cp-set of cardinality cpn(G) is called a cpn-set. A subset S of V is said to be a dom- chromatic set (or a dc-set) if S is a dominating set and χ(<S>) = χ(G). The minimum cardinality of a dom-chromatic set in a graph G is called the dom-chromatic number (or dc- number) of G and is denoted by γ_{ch}(G). The Kronecker product G_{1 }Ù G_{2} of two graphs G_{1 }= (V_{1}, E_{1}) and G_{2 }= (V_{2}, E_{2}) is the graph G with vertex set V_{1} x V_{2} and any two distinct vertices (u_{1}, v_{1}) and (u_{2}, v_{2}) of G are adjacent if u_{1}u_{2}Î E_{1} and v_{1}v_{2}Î E_{2}. The Cartesian product G_{1 }x G_{2} is the graph with vertex set V_{1 }x V_{2} where any two distinct vertices (u_{1}, v_{1}) and (u_{2}, v_{2}) are adjacent whenever (i) u_{1 }= u_{2} and v_{1}v_{2 }Î E_{2} or (ii) u_{1}u_{2}Î E_{1 }and v_{1} = v_{2}. These two products have no common edges. They are almost like complements but not exactly. In this paper, we discuss the behavior of the cp-number and dc-number and their bounds for product of paths in the two cases. A detailed comparative study is also done.

### References

T N Janakiraman and M Poobalaranjani, Dom-Chromatic sets in bipartite graphs. Int. J. Engg. Sci. Advanced Computing and Bio-technology, vol. 1, pp. 80-95, 2010.

T N Janakiraman and M Poobalaranjani, Dom-Chromatic sets of graphs. Int. J. Engg. Sci. Advanced Computing and Bio-technology, vol. 2, pp. 88-103, 2011.

G A Dirac, A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., vol. 27, pp. 85-92, 1952.

T N Janakiraman and M Poobalaranjani, On the chromatic preserving sets. Int. J. Engg. Sci. Advanced Computing and Bio-technology, vol. 1, pp. 29- 42, 2010.

W Imrich and H Izbicki, Associative products of graphs, Monatsh. Math., vol. 80, pp. 277–281, 1975.

P M Weishsel, The Kronecker product of graphs. Proc. Amer. Math. Soc., vol. 13, pp. 470-52, 1962.

S H Shapiro, The embedding of graphs in cubes and design of sequential relay circuits. Bell. Telephone Lab. Memorandum (unpublished report), 1953.

G Sabidussi. Graph multiplication. Math. Z., vol. 72, pp. 446-457, 1960.

H H Teh and H P Yap, Some construction problems of homogeneous graphs. Bull. Math. Soc., Nanyang Univ., pp. 164-196, 1964.

T W Haynes, S T Hedetniemi and P J Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York, 1998.

T Sitthiwirattham, Independednt and vertex covering number of Kronecker product of Km, n, Applied Mathematical Sciences, vol. 6, pp. 1403- 1408, 2012.

T Y Chang, W E Clark and E O Hare, Domination numbers of complete grid graphs-I, Dec. 19, 1995.