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

Authors

  • 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

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

D Delic and C Wang, The global connected domination in graphs (print).

F Harary, Graph Theory, Addison Wesley, Reading Mass, 1972.

J Clark and D A Holton, A First Look at Graph Theory, Allied Publishers Ltd., 1995

J P Joseph and S Arumugam, Domination and connectivity in graphs, International Journal of Management and Systems, vol. 8, pp. 233-236, 1992.

J P Joseph and S Arumugam, Domination and colouring in graphs, International Journal of Management and Systems, vol. 8, pp. 37-44, 1997.

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

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.

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.

G Mahadevan, “On domination theory and related topics in graphs”, Ph.D. Thesis, Manomaniam Sundaranar University, Tirunelveli, 2005.

E Sampathkumar, Global domination number of a graph, Journal Math. Phy. Sci., vol. 23, pp. 377-385, 1939.

Published

2012-08-27