pith. sign in

arxiv: 1710.02059 · v2 · pith:XATMYOEXnew · submitted 2017-10-05 · 🧮 math.CO

Graphs with equal domination and certified domination numbers

classification 🧮 math.CO
keywords dominationcertifiedrespectivelydominatinggammauppergraphnumber
0
0 comments X
read the original abstract

A set $D$ of vertices of a graph $G$ is a dominating set of $G$ if every vertex in $V_G-D$ is adjacent to at least one vertex in $D$. The domination number (upper domination number, respectively) of a graph $G$, denoted by $\gamma(G)$ ($\Gamma(G)$, respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of $G$. A subset $D\subseteq V_G$ is called a certified dominating set of $G$ if $D$ is a dominating set of $G$ and every vertex in $D$ has either zero or at least two neighbors in $V_G-D$. The cardinality of a~smallest (largest minimal, respectively) certified dominating set of $G$ is called the certified upper certified, respectively domination number of $G$ and is denoted by $\gamma_{\rm cer}(G)$ ($\Gamma_{\rm cer}(G)$, respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.