Connected Certified Domination in Graphs: Properties and Algorithmic Aspects
Abstract
A certified dominating set $D$ of a graph $\Gamma=(V_\Gamma,E_\Gamma)$ denoted by $\gamma_{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_{cer}^c-set)$ if $\mathcal{D}_c$ is $\gamma_{cer}-$set and $\Gamma[\mathcal{D}_c]$ is connected. Also, if $\mathcal{D}_c$ has no proper subset, then it is a smallest $\gamma_{cer}^c-$set, and the cardinality of the smallest $\gamma_{cer}^c-$set is called as connected certified domination number (CCDN) of the graph $\Gamma$ represented by $\gamma_{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 (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, Springer, Berlin, Heidelberg (1971), 55-61,
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. Lema´nska, J. Topp, R. Ziemann and P. Zyli´nski, Certified domina- ˙
tion, AKCE International Journal of Graphs and Combinatorics 17(1) (2020), 86-97,
doi:10.1016/j.akcej.2018.09.004.
M. Dettlaff, M. Lema´nska, M. Miotk, J. Topp, R. Ziemann and P. Zyli´nski, ˙
Graphs with equal domination and certified domination numbers arXiv preprint
arXiv:1710.02059 (2017), doi:10.48550/arXiv.1710.02059.
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-
X(03)00200-2.
Z. F¨uredi, A. V. Kostochka, R. Skrekovski, 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-
X(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.
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.
M. A. Henning and A. Yeo, Nordhaus-Gaddum Bounds for Total Domination,
In Total Domination in Graphs, Springer, New York, NY (2013), 125-129,
doi:10.1007/978-1-4614-6525-6-15.
T. W. Haynes, Domination in graphs: volume 2: advanced topics. Routledge, (2017), DominationinGraphs:Volume2:
AdvancedTopics-1stEdition-Zuhair(routledge.com)
T. W. Haynes, S. T. Hedetniemi and M. A. Henning, (Eds.), Topics in domination
in graphs, Vol. 64, Cham: Springer, (2020), doi:10.1007/978-3-030-51117-3.
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-
X(94)00373-Q.
A. Ilyass and V. S. Goswami, Connected certified domination number of certain
graphs, Advances and Applications of Mathematical Sciences 21(11) (2022), 6545-
, MiliPublications(mililink.com).
V.S. Goswami, A. ILyass and K.K. Bhagwat, September. Certified domination number of some graphs, In AIP Conference Proceedings, AIP Publishing 2735(1) (2023),
doi:10.1063/5.0140648.
R. Khoeilar, H. Karami, M. Chellali, S. M. Sheikholeslami and L. Volkmann,
Nordhaus-Gaddum type results for connected and total domination, RAIROOperations Research 55 (2021), S853-S862, doi:10.1051/ro/2020025.
J. P. Kumar, S. Arumugam and H. Khandelwal, Algorithmic aspects of certified
domination in graphs, Communications in Combinatorics and Optimization 7(2)
(2022), 247-255, doi:10.22049/CCO.2021.27302.1226.
A. I. Lone and V. S. 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
(1) (1982), 23-32, doi:10.1002/jgt.3190060104.
S. D. Raj and S. S. Kumari, Certified domination number in product of graphs, Turkish Journal of Computer and Mathematics Education (TURCOMAT) 11(3) (2020),
-1170, doi:10.17762/turcomat.v11i3.10298.
D. B. West, Introduction to graph theory, volume 2. Prentice hall Upper Saddle River
(2001), IntroductiontoGraphTheory(2ndedition)(illinois.edu).
R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer
Computations, Springer, 1972, pp. 85–103, doi:https://doi.org/10.1007/978-3-540-
-0 8.
M.E. Dyer and A.M. Frieze, Planar 3DM is NP-complete, Journal of Algorithms 73
(1986), 174-184, doi:https://doi.org/10.1016/0196-6774(86)90002-7
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.
