Certain domination numbers for Cartesian product of graphs

Arulanand, S.; Rajan, R. Sundara; Prabhu, S.; Stephen, Sudeep

doi:10.47974/JDMSC-1720

Open Access Research Article

Certain domination numbers for Cartesian product of graphs

S. Arulanandarulanand7875@gmail.comDepartment of MathematicsHindustan Institute of Technology and ScienceChennai, Tamil Nadu, 603103, India0000-0001-9862-0213View full profile → , ^*R. Sundara RajanCorresponding authorvprsundar@gmail.comDepartment of MathematicsHindustan Institute of Technology and ScienceChennai, Tamil Nadu, 603103, India0000-0002-1851-6334View full profile → , S. Prabhudrsavariprabhu@gmail.comDepartment of MathematicsRajalakshmi Engineering CollegeThandalam, Tamil Nadu, 602105, IndiaView full profile → , Sudeep StephenDepartment of MathematicsSchool of Computing ScienceUniversity of AucklandAuckland, 1010, New ZealandView full profile →

* Corresponding author · click or hover a name for details

pp. 1045–1058Vol. 27Issue 3April 2024DOI: 10.47974/JDMSC-1720 Crossmark XML

Received:: 08 Jun 2022
Accepted:: 11 Oct 2022
Published Online:: 02 Apr 2024
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1720
Pages:: 1045–1058

Abstract

Let G be a network, any node v ϵ V(G)\D is adjacent to atleast one node in D, then the set D is named a dominating set, represented by γ(G). A set D of nodes in a network G is called an independent dominating set if D is an independent set. A total dominating set of a network G is a set D of nodes such that every nodes in G is adjacent to a node in D. A dominating set D of G is called paired dominating set whose induced graph of D contains a perfect matching. A 2-dominating set of a network G is a dominating set, in which any node not in D has minimum two neighbours in D. The minimal size of a 2-dominating set of G denoted by γ2(G), is the 2-domination number of G. In this paper, we obtain certain domination parameters, such as domination, independent domination, total domination and paired domination numbers for the class of Cartesian product of cycle Cm, and circulant graph G(6n; ±{1, 2}) and G(8n; ±{1, 2, 3}) where m ≡ 0(mod 4), n ≥ 1 and there by proving that the cardinality of all parameters are same for the above graphs. And also we obtain 2-domination number for the Cartesian product of cycle Cm, and circulant graph G(2n; ±{1, 2}), with m ≡ 0(mod 4), and Cartesian product of cycle Cm, and circulant graph G(2n; ±{1, 3}), with m ≡ 0, 2(mod 4), n ≥ 3, Furthermore, we demonstrating that the lower bound found in [1], [2], and [3] are quite precise for the results obtained here for domination and independent domination, total and paired domination, and 2-domination respectively.

Keywords

Domination Independent domination Total domination Paired domination 2-domination Cartesian product Cycle Circulant graph

Subject Classifications

05C6905C7605C90

References

[1] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Mathematics, 313(7) 839–854 (2013).
[2] M.A. Henning and A. Yeo, Total Domination and Graph Products. In Total Domination in Graphs, Springer, 103–108 (2013).
[3] J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and Forbidden Subgraphs. In Graph theory with Application to Algorithm and Computer Science, Wiley, New York, 282–300 (1985).
[4] E. Cockayne and S. Hedetniemi, Towards a theory of domination in graphs, Networks, 7(3), 247–261 (1977).
[5] D. Vuki and A. Klobu, K-dominating sets on linear benzenoids and on the infinite hexagonal grid, Croatica Chemica Acta, 80(2), 187–191 (2007).
[6] J.L. Hurink and T. Nieberg, Approximating minimum independent dominating sets in wireless networks, Information Processing Letters, 109, 155–160 (2008).
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, CRC Press, Boca Raton, (1998).
[8] C.F. De Jaenisch, Traité des Applications de l’ Analyse Mathématique au jeu des Échecs, Dufour et cie, (1862).
[9] E.j. Cockayne and S.T. Hedetniemi, Independence graphs, Congressus Numerantium, 471–491 (1974).
[10] D.Anandhababu, M. Priyadharshini, and N. Parvathi, On independent domination parameters of some special families of Halin graph, Journal of Discrete Mathematical Sciences and Cryptography, 22(6), 1113–1119 (2019).
[11] E.J. Cockayne, R.S. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks, 10(3), 211–219 (1980).
[12] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Mathematics, 309(1), 32–63 (2009).
[13] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks, 32, 199-209 (1998).
[14] C. Bujtás and S. Jaskóa, Bounds on the 2-domination number, Discrete Applied Mathematics, 242, 4–15 (2018).
[15] J.M. Xu, Topological structure and analysis of interconnection networks, Kluwer Academic Publishers, Netherlands, (2001).
[16] J.C. Bermond, F. Comellas, and D.F. Hsu, Distributed loop computers-networks: A survey, Journal of Parallel and Distributed Computing, 24, 2–10 (1995).
[17] N. Obradović, J. Peters, and G. Ružić, Efficient domination in circulant graphs with two chord lengths, Information Processing Letters, 102, 253–258 (2007).
[18] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy, 9, 30–43 (1963).
[19] B.L. Hartnell and D.F. Rall, Domination in Cartesian products: Vizing’s conjecture, in: Domination in Graphs-Advanced Topics, Marcel Dekker, New York, 163–189 (1998).
[20] M.H. Zahar, S.M. Khamis, and K.M. Nazzal, On the domination number of the Cartesian product of the cycle of length n and any graph, Discrete Applied Mathematics, 155, 515–522 (2007).
[21] X. Hou and Y. Lu, On the {k}-domination number of Cartesian product of graphs, Discrete Mathematics, 309, 3413–3419 (2009).
[22] K. Choudhary, S. Margulies, and I.V. Hicks, Interger domination of Cartesian product of graphs, Discrete Mathematics, 338, 1239–1242 (2015).
[23] X. Chen, X. Li, J. Wang and N. Fan, The rainbow connectivity of Cartesian product graphs, Journal of Discrete Mathematical Sciences and Cryptography, 22(6), 901–914 (2019).
[24] B. Bresar, Paired domination of Cartesian product of graphs and rainbow domination, Electronic Notes in Discrete Mathematics, 22, 233–237 (2005).
[25] M. Blidia, M. Chellali, and O.Favaron, Independence and 2-domination in trees, Australasian Journal of Combinatorics, 33, 317–327 (2005).
[26] A. Hansberge and L. Volkmann, On graphs with equal domination and 2-domination numbers, Discrete Mathematics, 308, 2277–2281 (2008).
[27] R.S. Shaheen, Bounds for the 2-domination number of toroidal grid graphs, International Journal of Computer Mathematics, 86 584–588 (2009).
[28] M. Rao and A. Talon, The 2-domination and Roman domination numbers of grid graphs, Discrete Mathematics and Theoretical Computer Science, 21, 5–14 (2019).
[29] C. Brause, M.A. Henning, and M. Krzywkowski, A characterization of trees with equal 2-domination and 2-independence numbers, Discrete Mathematics and Theoretical Computer Science, 19, 263–270 (2017).
[30] J. Fujisawa, A. Hansberg, T. Kubo, A. Saito, M. Sugita, and L. Volkmann, Independence and 2-domination in bipartite graphs, Australasian Journal of Combinatorics, 40, 265–268 (2008).
[31] S.F. Hwang and G.J. Chang, The k- neighbor domination problem, European Journal of Operational Research, 52, 373–377 (1991).
[32] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Mathematica, 26(1), 5–125321 (2006).

Views: 1,064Downloads: 158Citations: 0