Connected Certified Domination in Graphs: Properties and Algorithmic Aspects
DOI:
https://doi.org/10.26713/cma.v15i2.2630Keywords:
Dominating set, Certified Dominating Set (CFDS), Connected Certified Dominating Set (CCDS), Nordhaus-Gaddum resultsAbstract
A certified dominating set \(D\) of a graph \(\Gamma=(V_\Gamma,E_\Gamma)\) denoted by \(\gamma_{\mathit{cer}}\)-set, is the subset of \(V_\Gamma\) such that \(|N(u)\cap(V_\Gamma-D)|\) is either \(0\) or \(2\), \(\forall\) \(u\in D\). A set \(\mathcal{D}_c\subseteq V_\Gamma\) is called a connected certified dominating set \((\gamma_{\mathit{cer}}^c\)-set\()\) if \(\mathcal{D}_c\) is \(\gamma_{\mathit{cer}}\)-set and \(\Gamma[\mathcal{D}_c]\) is connected. Also, if \(\mathcal{D}_c\) has no proper subset, then it is a smallest \(\gamma_{\mathit{cer}}^c\)-set, and the cardinality of the smallest \(\gamma_{\mathit{cer}}^c\)-set is called as connected certified domination number (CCDN) of the graph \(\Gamma\) represented by \(\gamma_{\mathit{cer}}^c(\Gamma)\). In this article, we continue the study of connected certified domination. Herein, we classify graphs with larger values of CCDN and then we will study some properties of connected certified domination. Moreover, we will provide upper bounds and Nordhaus-Gaddum results for the CCDN. Additionally, we will prove that the connected certified domination problem is NP-complete for star convex bipartite graphs, comb convex bipartite graphs, and planar graphs.
Downloads
References
M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Applied Mathematics 161(4-5) (2013), 466 – 546, DOI: 10.1016/j.dam.2011.12.018.
G. Chartrand and J. Mitchem, Graphical theorems of the Nordhaus-Gaddum class, in: Recent Trends in Graph Theory, M. Capobianco, J. B. Frechen and M. Krolik (editors), Lecture Notes in Mathematics, Vol. 186, Springer, Berlin — Heidelberg, DOI: 10.1007/BFb0059422.
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.
M. Dettlaff, M. Lemanska, J. Topp, R. Ziemann and P. Zylinski, Certified domination, AKCE International Journal of Graphs and Combinatorics 17(1) (2020), 86 – 97, DOI: 10.1016/j.akcej.2018.09.004.
M. Dettlaff, M. Lemanska, M. Miotk, J. Topp, R. Ziemann and P. Zylinski, Graphs with equal domination and certified domination numbers, Opuscula Mathematica 39(6) (2019), 815 – 827, DOI: 10.7494/OpMath.2019.39.6.815.
M. E. Dyer and A. M. Frieze, Planar 3DM is NP-complete, Journal of Algorithms 7(2) (1986), 174 – 184, DOI: 10.1016/0196-6774(86)90002-7.
S. Erfang, D. Chuangyin and K. Liying, A note on Nordhaus-Gaddum inequalities for domination, Discrete Applied Mathematics 136(1) (2004), 83 – 85, DOI: 10.1016/S0166-218X(03)00200-2.
Z. Füredi, A. V. Kostochka, R. Škrekovski, M. Stiebitz and D. B. West, Nordhaus-Gaddum-type theorems for decompositions into many parts, Journal of Graph Theory 50(4) (2005), 273 – 292, DOI: 10.1002/jgt.20113.
W. Goddard and M. A. Henning, Nordhaus-Gaddum bounds for independent domination, Discrete Mathematics 268(1-3) (2003), 299 – 302, DOI: 10.1016/S0012-365X(03)00032-3.
W. Goddard, M. A. Henning and H. C. Swart, Some Nordhaus-Gaddum-type results, Journal of Graph Theory 16(3) (1992), 221 – 231, DOI: 10.1002/jgt.3190160305.
V. S. Goswami, A. Ilyass and K. K. Bhagwat, Certified domination number of some graphs, AIP Conference Proceedings 2735 (2023), 040029, DOI: 10.1063/5.0140648.
F. Harary and T. W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Mathematics 155(1-3) (1996), 99 – 105, DOI: 10.1016/0012-365X(94)00373-Q.
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.
T. W. Haynes, Domination in Graphs, Volume 2: Advanced Topics, 1st edition, Routledge, 520 pages (2017), DOI: 10.1201/9781315141428.
T. W. Haynes, S. T. Hedetniemi and M. A. Henning (editors), Topics in Domination in Graphs, Vol. 64, Springer Cham., viii + 545 pages (2020), DOI: 10.1007/978-3-030-51117-3.
M. A. Henning, E. J. Joubert and J. Southey, Nordhaus-Gaddum bounds for total domination, Applied Mathematics Letters 24(6) (2011), 987 – 990 DOI: 10.1016/j.aml.2011.01.011.
A. Ilyass and V. S. Goswami, Connected certified domination number of certain graphs, AIP Conference Proceedings 2735 (2023), 040028, DOI: 10.1063/5.0140647.
P. K. Jakkepalli, S. Arumugam, H. Khandelwal and V. S. Reddy, Algorithmic aspects of certified domination in graphs, Communications in Combinatorics and Optimization 7(2) (2022), 247 – 255, DOI: 10.22049/CCO.2021.27302.1226.
R. M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, 50 Years of Integer Programming 1958-2008, M. Jünger et al. (editors), Springer, Berlin, Heidelberg, pp. 219 – 241 (2010), DOI: 10.1007/978-3-540-68279-0_8.
R. Khoeilar, H. Karami, M. Chellali, S. M. Sheikholeslami and L. Volkmann, Nordhaus-Gaddum type results for connected and total domination, RAIRO-Operations Research 55 (2021), S853 – S862, DOI: 10.1051/ro/2020025.
A. I. Lone and V. Goswami, Connected certified domination edge critical and stable graphs, Acta Universitatis Sapientiae Informatica 15(1) (2023), 25 – 37, DOI: 10.2478/ausi-2023-0003.
E. A. Nordhaus and J. W. Gaddum, On complementary graphs, The American Mathematical Monthly 63(3) (1956), 175 – 177, DOI: 10.2307/2306658.
C. Payan and N. H. Xuong, Domination-balanced graphs, Journal of Graph Theory 6(1) (1982), 23 – 32, DOI: 10.1002/jgt.3190060104.
S. D. Raj and S. G. S. Kumari, Certified domination number in product of graphs, Turkish Journal of Computer and Mathematics Education (TURCOMAT) 11(3) (2020), 1166 – 1170, DOI: 10.17762/turcomat.v11i3.10298.
D. B. West, Introduction to Graph Theory, 2nd edition, Pearson Education, India (2002).
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
