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

The Graphs Whose Sum of Global Connected Domination Number and Chromatic Number is 2n-5

  • Mahadevan G,
  • A Selvam Avadayappan,
  • Twinkle Johns
Mahadevan G
Department of Mathematics, Anna University, Tirunelveli, India.
A Selvam Avadayappan
Department of Mathematics, VHNSN College, Virdhunagar, India.
Twinkle Johns
Department of Mathematics, VPMM Engineering College for Women, Krishnankoil, Tamilnadu,India.
DOI: https://doi.org/10.12723/mjs.23.7

Published 2012-08-27

Keywords

  • Global connected domination number,
  • chromatic number AMS subject Classification,
  • 05C (primary)

Abstract

A subset S of vertices in a graph G = (V,E) is a dominating set if every vertex in V-S is adjacent to atleast one vertex in S. A dominating set S of a connected graph G is called a connected dominating set if the induced sub graph < S > is connected. A set S is called a global dominating set of G if S is a dominating set of both G and . A subset S of vertices of a graph G is called a global connected dominating set if S is both a global dominating and a connected dominating set. The global connected domination number is the minimum cardinality of a global connected dominating set of G and is denoted by γgc(G). In this paper we characterize the classes of graphs for which γgc(G) + χ(G) = 2n-5 and 2n-6 of global connected domination number and chromatic number and characterize the corresponding extremal graphs.

References

  1. D Delic and C Wang, The global connected domination in graphs (print).
  2. F Harary, Graph Theory, Addison Wesley, Reading Mass, 1972.
  3. J Clark and D A Holton, A First Look at Graph Theory, Allied Publishers Ltd., 1995
  4. J P Joseph and S Arumugam, Domination and connectivity in graphs, International Journal of Management and Systems, vol. 8, pp. 233-236, 1992.
  5. J P Joseph and S Arumugam, Domination and colouring in graphs, International Journal of Management and Systems, vol. 8, pp. 37-44, 1997.
  6. J P Joseph and G Mahadevan, Complementary Connected Domination Number Andchromatic Number of a Graph: Mathematical and Computational Models, Allied Publications, India, pp. 342-349, 200
  7. J P Joseph, G Mahadevan and A Selvam, On complementary perfect domination number of a graph, Acta Ciencia Indica, Vol XXXI M, pp. 847, 2006.
  8. G Mahadevan, A Selvam and M Hajmeeral, On efficient domination number and chromatic number of a graph I, International Journal of Physical Sciences, vol. 21 M, pp. 1-8, 2009.
  9. G Mahadevan, “On domination theory and related topics in graphs”, Ph.D. Thesis, Manomaniam Sundaranar University, Tirunelveli, 2005.
  10. E Sampathkumar, Global domination number of a graph, Journal Math. Phy. Sci., vol. 23, pp. 377-385, 1939.