The Graphs Whose Sum of Global Connected Domination Number and Chromatic Number is 2n-5
DOI:
https://doi.org/10.12723/mjs.23.7Keywords:
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.