Vol. 11 No. 4 (2012): Mapana Journal of Sciences
Research Articles

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

  • T N Janakiraman,
  • M Poobalaranjani
T N Janakiraman
Department of Mathematics, National Institute of Technology, Tiruchirapalli-620015, India.
M Poobalaranjani
Seethalakshmi Ramaswami College, Tiruchirapalli-620002, India;
DOI: https://doi.org/10.12723/mjs.23.3

Published 2012-07-23

Keywords

  • Cp-set,
  • cp-number,
  • dom-chromatic set,
  • dom-chromatic number,
  • Kronecker product,
  • Cartesian product
    • ...More
    Less

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. W Imrich and H Izbicki, Associative products of graphs, Monatsh. Math., vol. 80, pp. 277–281, 1975.
  6. P M Weishsel, The Kronecker product of graphs. Proc. Amer. Math. Soc., vol. 13, pp. 470-52, 1962.
  7. S H Shapiro, The embedding of graphs in cubes and design of sequential relay circuits. Bell. Telephone Lab. Memorandum (unpublished report), 1953.
  8. G Sabidussi. Graph multiplication. Math. Z., vol. 72, pp. 446-457, 1960.
  9. H H Teh and H P Yap, Some construction problems of homogeneous graphs. Bull. Math. Soc., Nanyang Univ., pp. 164-196, 1964.
  10. T W Haynes, S T Hedetniemi and P J Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York, 1998.
  11. T Sitthiwirattham, Independednt and vertex covering number of Kronecker product of Km, n, Applied Mathematical Sciences, vol. 6, pp. 1403- 1408, 2012.
  12. T Y Chang, W E Clark and E O Hare, Domination numbers of complete grid graphs-I, Dec. 19, 1995.