On the domination number of a graph and its square graph
Main Article Content
Abstract
For a given graph $G=(V, E),$ a dominating set is a subset $V'$ of the vertex set $V$ so that each vertex in $V \setminus V'$ is adjacent to a vertex in $V'.$ The minimum cardinality of a dominating set of $G$ is called the \textit{domination number} of $G$ and is denoted by $\gamma(G).$ For an integer $k \geq 1,$ the \textit{k-th power} $G^k$ of a graph $G$ with $V(G^k)=V(G)$ for which $uv \in E(G^k)$ if and only if $1 \leq d_{G}(u,v) \leq k.$ Note that $G^2$ is the square graph of a graph $G.$ In this paper, we obtain some tight bounds for the sum of the domination numbers of a graph and its square graph in terms of the order, order and size, and maximum degree of the graph $G.$ Also, we characterize such 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] C. Berge, Theory of Graphs and Its Applications, Hethuen, London, 1962. Google Scholar
[3] J. A. Bondy and U. S. R. Murty, Graph Theory, Spinger, 2008. Google Scholar
[4] E. J. Cockayne, T. W. Haynes and S. T. Hedetniemi, Extremal graphs for inequalities involving domination parameters, Discrete. Math, 216 (2000), 1–10. Google Scholar
[5] J. F. Frank, M. S. Jacobson, L. F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar, 16 287–293. Google Scholar
[6] W. Goddard and M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory, 40 (2002) 1–25. Google Scholar
[7] T. W. Haynes, S. T. Hedetnimi and P. J. Slater, Fundamentals of domination in graphs, New York, Marcel Dekkar, Inc., 1998. Google Scholar
[8] 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
[9] G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory, 22 (1996), 213–229. Google Scholar
[10] 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
[11] 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, pages 170–181. Google Scholar
[12] 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
[13] 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
[14] E. Murugan and J. Paulraj Joseph, On the Domination Number of a Graph and its Block Graph, Discrete Mathematics, Algorithms and Applications, (Accepted) 2021. Google Scholar
[15] E. A. Nordhaus and J. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956), 177–182. Google Scholar
[16] O. Ore, Theory of Graphs, Am. Math. SOC. Colloq. Publ, 38, Providence, RI, 1962. Google Scholar
[17] C. Payan and N. H. Xuong, Domination-balanced graphs, J. Graph Theory, 6 (1982), 23–32. Google Scholar
[18] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete. Math, 191 (1998), 173–179. Google Scholar
[19] H. B. Walikar, B. D. Acharya and E. Sampathkumar, Recent developements in the theory of domination in graphs, In MRI Lecture Notes in Math, Mahta Research Instit, Allahabad, 01, 1979. Google Scholar