Certified domination

DOI10.1016/J.AKCEJ.2018.09.004MaRDI QIDQ5154565zbMATH OpenOpenAlexWikidataFDO

Authors Magda Dettlaff, Magdalena Lemańska, Jerzy Topp, Radosław Ziemann, Paweł Żyliński

Publication date 5 October 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1606.03257

zbMATH Keywords

coronadominationNordhaus-Gaddum-type inequalitiescertified domination

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Imagine that we are given a set $D$ of officials and a set $W$ of civils. For each civil $xinW$, there must be an official $vinD$ that can serve $x$, and whenever any such $v$ is serving $x$, there must also be another civil $winW$ that observes $v$, that is, $w$ may act as a kind of witness, to avoid any abuse from $v$. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce the concept of certified domination that perfectly models the aforementioned problem. Specifically, a dominating set $D$ of a graph $G=(V_G,E_G)$ is said to be certified if every vertex in $D$ has either zero or at least two neighbours in $V_{G}setminusD$. The cardinality of a minimum certified dominating set in $G$ is called the certified domination number of $G$. Herein, we present the exact values of the certified domination number for some classes of graphs as well as provide some upper bounds on this parameter for arbitrary graphs. We then characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We also provide Nordhaus-Gaddum type inequalities for the certified domination number. Finally, we show that the (decision) certified domination problem is NP-complete.

Recommendations

• Graphs with equal domination and certified domination numbers
• scientific article; zbMATH DE number 3873384
• Domination in Graphs
• Co-secure and secure domination in graphs
• Paired-domination in graphs

Cites work

• scientific article; zbMATH DE number 6096635 (Why is no real title available?)
• scientific article; zbMATH DE number 4008449 (Why is no real title available?)
• scientific article; zbMATH DE number 3536146 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 2188609 (Why is no real title available?)
• scientific article; zbMATH DE number 3358515 (Why is no real title available?)
• A characterization of \((2\gamma ,\gamma _{\text p})\)-trees
• A characterization of \((\gamma_t,\gamma_2)\)-trees
• A survey of Nordhaus-Gaddum type relations
• Constructing connected bicritical graphs with edge-connectivity 2
• Edge criticality in secure graph domination
• On Complementary Graphs
• On graphs having domination number half their order
• On graphs with disjoint dominating and 2-dominating sets
• Total domination edge critical graphs with total domination number three and many dominating pairs
• Total outer-connected domination in trees
• Towards a theory of domination in graphs
• Vertex domination-critical graphs
• Vertex domination‐critical graphs
• Well irredundant graphs

Cited in

(5)

• Domination cover rubbling
• Dominance made simple
• Graphs with equal domination and certified domination numbers
• Connected certified domination edge critical and stable graphs
• Algorithmic aspects of certified domination in graphs

This page was built for publication: Certified domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5154565)