Nordhaus-Gaddum type results for connected domination number of graphs
Main Article Content
Abstract
Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is called a dominating set of $G$ if every vertex not in $S$ is adjacent to some vertex in $S.$ The domination number $\gamma(G)$ of $G$ is the minimum cardinality taken over all dominating sets of $G.$ A dominating set $S$ is called a connected dominating set if the subgraph induced by $S$ is connected. The minimum cardinality taken over all connected dominating sets of $G$ is called the connected domination number of $G,$ and is denoted by $\gamma_c(G).$ In this paper, we investigate the Nordhaus-Gaddum type results for the connected domination number and its derived graphs like line graph, subdivision graph, power graph, block graph and total graph, and characterize the extremal graphs.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.
References
[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Applied Mathematics. 161 (4-5) (2013), 466–546. Google Scholar
[2] S. Arumugam and J. Paulraj Joseph, Domination in Subdivision Graphs, Journal of Indian Math Soc. 62 (1-4) (1996), 274–282. Google Scholar
[3] S. Arumugam and S. Velammal, Connected Edge Domination in Graphs, Bulletin of the Allahabad Mathematical Society Pramila Srivastava Memorial Volume. 24 (1) (2009), 43–49. Google Scholar
[4] M. Behzad, A criterion for the planarity of a total graph, Proc. Cambridge Philos. Soc. 63 (1967), 679–681. Google Scholar
[5] C. Berge, Theory of Graphs and Its Applications, London, Hethuen, 1962. Google Scholar
[6] J. A. Bondy and U. S. R. Murty, Graph Theory, London, Spinger, 2008. Google Scholar
[7] M. B. Cozzens and L. L. Kelleher, Dominating cliques in graphs, Discrete Math. 86 (1990), 145–164. Google Scholar
[8] Frank Harary, Graph Theory, Addison-Wesley Publishing Company, London, 1969. Google Scholar
[9] Gary Chartrand and Ping Zhang, Introduction To Graph Theory, Tata McGraw-Hill, 2006. Google Scholar
[10] T. W. Haynes, S. T. Hedetnimi and P. J. Slater, Fundamentals of domination in graphs, New York, Marcel Dekkar, Inc., 1998. Google Scholar
[11] S. T. Hedetniemi and R. C. Laskar, Connected domination in graphs, In B. Bollobas, editor, Graph Theory and Combinatorics, Academic Press. London, 1984, 209–218. Google Scholar
[12] F. Jaeger and C. Payan, Relations due Type Nordhaus-Gaddum pour le Nombre d’Absorption d’un Graphe Simple, C. R. Acad. Sci. Paris Ser. A. 274 (1972), 728–730. Google Scholar
[13] B. S. Karunagaram and J. Paulraj Joseph, On Domination Parameters and Maximum Degree of a Graph, Journal of Discrete Mathematical Sciences & Cryptography. 9 (2) (2006), 215–223. Google Scholar
[14] G. Mahadevan, Selvam Avadayappan, J. Paulraj Joseph, B. Ayisha and T. Subramanian, Complementary Triple Connected Domination Number of a Graph, Advances and Applications in Discrete Mathematics. 12 (1) (2013), 39–54. Google Scholar
[15] Moo Young Sohn, Sang Bum Kim, Young Soo Kwon and Rong Quan Feng, Classification of Regular Planar Graphs with Diameter Two, Acta Mathematica Sinica, English Series. 23 (3) (2007), 411–416. Google Scholar
[16] E. Murugan and J. Paulraj Joseph, On the domination number of a graph and its line graph, International Journal of Mathematical Combinatorics. Special Issue 1, (2018), 170–181. Google Scholar
[17] E. Murugan and J. Paulraj Joseph, On the Domination Number of a Graph and its Total Graph, Discrete Mathematics, Algorithms and Applications. 12(5) (2020) 2050068. Google Scholar
[18] E. Murugan and G. R. Sivaprakash, On the Domination Number of a Graph and its Shadow Graph, Discrete Mathematics, Algorithms and Applications. 13 (6) (2021) 2150074. Google Scholar
[19] E. Murugan and J. Paulraj Joseph, On the Domination Number of a Graph and its Block Graph, Discrete Mathematics, Algorithms and Applications. 14 (7) (2022) 2250033. Google Scholar
[20] E. A. Nordhaus and J. Gaddum, On complementary graphs, Amer. Math. Monthly. 63 (1956) 177–182. Google Scholar
[21] O. Ore, Theory of Graphs, Am. Math. SOC. Colloq. Publ. 38, Providence, RI, 1962. Google Scholar
[22] E. Sampathkumar and H. B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607–613. Google Scholar
[23] W. J. Desormeaux, T. W. Haynes and M. A. Henning, Bounds on the connected domination number of a graph, Discrete Applied Mathematics 161 (2013), 2925–2931. Google Scholar