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

  • T N Janakiraman Department of Mathematics, National Institute of Technology, Tiruchirapalli-620015, India.
  • M Poobalaranjani Seethalakshmi Ramaswami College, Tiruchirapalli-620002, India;
Keywords: Cp-set, cp-number, dom-chromatic set, dom-chromatic number, Kronecker product, Cartesian product

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 G1 Ù G2 of two graphs G1 = (V1, E1) and G2 = (V2, E2) is the graph G with vertex set V1 x V2 and any two distinct vertices (u1, v1) and (u2, v2) of G are adjacent if u1u2Î E1 and v1v2Î E2. The Cartesian product G1 x G2 is the graph with vertex set V1 x V2 where any two distinct vertices (u1, v1) and (u2, v2) are adjacent whenever (i) u1 = u2 and v1v2 Î E2 or (ii) u1u2Î E1 and v1 = v2. 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.

Published
2012-07-23
Section
Research Articles