Certified domination

Figures & data

Fig. 1 The family of graphs $G_i$. (a) Black vertices form a certified dominating set $D_{\mathrm{c}}$ with $\left|D_{\mathrm{c}}\right|=i+3$, $i\ge 2$. (b) Black and grey vertices form a $(D,D_2)$-pair, respectively, with $\left|D\right|=2i+1$. Observe that if $i\ge 3$, then $G_i$ has no $(D,D_2)$-pair with $\left|D\right|\le i+3$.

Fig. 2 The diadem graph resulting from the corona $G=(K_3\cup K_2)\circ K_1$ by adding a leaf to the support vertex $s$ of $G$.

Fig. 3 Adding or deleting an edge may arbitrarily increase the certified domination number.

Fig. 4 Graph $G_i$ has $2i+1$ vertices, and ${\gamma }_{\mathrm{cer}}\left(G_i\right)=i$, while ${\gamma }_{\mathrm{cer}}(G_i+v)=2i+2$.

Fig. 5 Tree $T_i=S(P_{2i+1}\circ K_1)$ in which black vertices form a $\gamma$-set and a ${\gamma }_{\mathrm{cer}}$-set, respectively.