Certified domination

DOI10.1016/J.AKCEJ.2018.09.004zbMATH Open1473.05221arXiv1606.03257OpenAlexW3037635478WikidataQ129164574 ScholiaQ129164574MaRDI QIDQ5154565FDOQ5154565

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex domination-critical graphs
• Towards a theory of domination in graphs
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• Title not available (Why is that?)
• On graphs having domination number half their order
• Well irredundant graphs
• Constructing connected bicritical graphs with edge-connectivity 2
• Vertex domination‐critical graphs
• Title not available (Why is that?)
• Total domination edge critical graphs with total domination number three and many dominating pairs
• Edge criticality in secure graph domination
• Total outer-connected domination in trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of \((\gamma_t,\gamma_2)\)-trees
• A characterization of \((2\gamma ,\gamma _{\text p})\)-trees
• On graphs with disjoint dominating and 2-dominating sets
• Title not available (Why is that?)

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)