Restrained and Total Restrained Domination of Ladder Graphs

N. C. Hemalatha; S. B. Chandrakala; B. Sooryanarayana; M. Vishu Kumar

doi:10.26713/cma.v14i4.2569

Authors

N. C. Hemalatha Department of Mathematics, Oxford College of Engineering, Bengaluru, Karnataka, India https://orcid.org/0000-0002-3121-623X (unauthenticated)
S. B. Chandrakala Department of Mathematics, Nitte Meenakshi Institute of Technology, Bengaluru, Karnataka, India https://orcid.org/0000-0002-4868-4187 (unauthenticated)
B. Sooryanarayana Department of Mathematics, Dr. Ambedkar Institute of Technology, Bengaluru, Karnataka, India https://orcid.org/0000-0002-2835-2855 (unauthenticated)
M. Vishu Kumar Department of Mathematics, REVA University, Bengaluru, Karnataka, India https://orcid.org/0000-0003-0719-3637 (unauthenticated)

DOI:

https://doi.org/10.26713/cma.v14i4.2569

Keywords:

Domination, Total domination, Restrained domination

Abstract

Telle and Proskurowksi introduced restrained domination as a vertex partition problem in partial \(k\)-tress (Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM Journal on Discrete Mathematics 10(4) (1997), 529 - 550). For a graph \(G(V,E)\), a restrained domination number is the minimum cardinality of a subset \(\mathfrak{D}\) of \(V\) such that for every vertex \(v\in \bar{\mathfrak{D}}\) there is a vertex in \(\mathfrak{D}\) as well as in \(\bar{\mathfrak{D}}\) adjacent to \(v\). If \(\mathfrak{D}\) satisfies an additional condition that every vertex of \(V\) has a neighbor in \(\mathfrak{D}\), then \(\mathfrak{D}\) is said to be a total restrained dominating set. Minimum cardinality of \(\mathfrak{D}\) is said to be total restrained domination number of graph \(G\). In this paper we have obtained domination, restrained, total and total restrained domination number of some ladder graphs.

Views: 844Downloads: 479

Downloads

Download data is not yet available.

References

E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10(3) (1980), 211 – 219, DOI: 10.1002/net.3230100304.

J. Cyman and J. Raczek, On the total restrained domination number of a graph, The Australasian Journal of Combinatorics 36 (2006), 91 – 100, URL: http://ajc.maths.uq.edu.au/pdf/36/ajc_v36_p091.pdf.

G. S. Domke, J. H. Hattingh, M. A. Henning and L. R. Markus, Restrained domination in trees, Discrete Mathematics 211(1-3) (2000), 1 – 9, DOI: 10.1016/S0012-365X(99)00036-9.

G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar and L. R. Markus, Restrained domination in graphs, Discrete Mathematics 203(1-3) (1999), 61 – 69, DOI: 10.1016/S0012-365X(99)00016-3.

J. H. Hattingh and A. R. Plummer, A note on restrained domination in trees, Ars Combinatoria XCIV (2010), 477 – 483, URL: https://combinatorialpress.com/ars/arch/vol94/.

J. H. Hattingh and E. J. Joubert, An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree, Discrete Applied Mathematics 157(13) (2009), 2846 – 2858, DOI: 10.1016/j.dam.2009.03.010.

J. H. Hattingh and E. J. Joubert, Restrained domination in claw-free graphs with minimum degree at least two, Graphs and Combinatorics 25 (2009), 693 – 706, DOI: 10.1007/s00373-010-0883-3.

J. H. Hattingh and E. J. Joubert, Restrained domination in cubic graphs, Journal of Combinatorial Optimization 22 (2011), 166 – 179, DOI: 10.1007/s10878-009-9281-2.

J. H. Hattingh, E. Jonck and E. J. Joubert, Bounds on the total restrained domination number of a graph, Graphs and Combinatorics 26 (2010), 77 – 93, DOI: 10.1007/s00373-010-0894-0.

J. H. Hattingh, E. Jonck, E. J. Joubert and A. R. Plummer, Nordhaus–Gaddum results for restrained domination and total restrained domination in graphs, Discrete Mathematics 308(7) (2008), 1080 – 1087, DOI: 10.1016/j.disc.2007.03.061.

J. H. Hattingh, E. Jonck, E. J. Joubert and A. R. Plummer, Total restrained domination in trees, Discrete Mathematics 307(13) (2007), 1643 – 1650, DOI: 10.1016/j.disc.2006.09.014.

T. W. Haynes, S. T. Hedetniemi and M. A. Henning (editors), Topics in Domination in Graphs, 1st edition, Developments in Mathematics series (DEVM, Vol. 64), Springer Cham, viii + 545 pages (2020), DOI: 10.1007/978-3-030-51117-3.

M. A. Henning, Graphs with large restrained domination number, Discrete Mathematics 197-198 (1999), 415 – 429, DOI: 10.1016/S0012-365X(99)90095-X.

M. A. Henning and J. E. Maritz, Total restrained domination in graphs with minimum degree two, Discrete Mathematics 308(10) (2008), 1909 – 1920, DOI: 10.1016/j.disc.2007.04.039.

J. Raczek and J. Cyman, Total restrained domination numbers of trees, Discrete Mathematics 308(1) (2008), 44 – 50, DOI: 10.1016/j.disc.2007.03.041.

J. A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM Journal on Discrete Mathematics 10(4) (1997), 529 – 550, DOI: 10.1137/S0895480194275825.