TY - JOUR
ID - 13553
TI - Hypo-efficient domination and hypo-unique domination
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Samodivkin, Vladimir
AD - University of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics
Y1 - 2016
PY - 2016
VL - 1
IS - 2
SP - 103
EP - 116
KW - Domination number
KW - Efficient Domination
KW - unique domination
KW - hypo-property
DO - 10.22049/cco.2016.13553
N2 - For a graph $G$ let $\gamma (G)$ be its domination number. We define a graph G to be (i) a hypo-efficient domination graph (or a hypo-$\mathcal{ED}$ graph) if $G$ has no efficient dominating set (EDS) but every graph formed by removing a single vertex from $G$ has at least one EDS, and (ii) a hypo-unique domination graph (a hypo-$\mathcal{UD}$ graph) if $G$ has at least two minimum dominating sets, but $G-v$ has a unique minimum dominating set for each $v\in V(G)$. We show that each hypo-$\mathcal{UD}$ graph $G$ of order at least $3$ is connected and $\gamma(G-v) <\gamma(G)$ for all $v \in V$. We obtain a tight upper bound on the order of a hypo-$\mathcal{P}$ graph in terms of the domination number and maximum degree of the graph, where $\mathcal{P} \in \{\mathcal{UD}, \mathcal{ED}\}$. Families of circulant graphs, which achieve these bounds, are presented. We also prove that the bondage number of any hypo-$\mathcal{UD}$ graph is not more than the minimum degree plus one.
UR - https://comb-opt.azaruniv.ac.ir/article_13553.html
L1 - https://comb-opt.azaruniv.ac.ir/article_13553_2afb7e049e6640f7612ba8d81256137c.pdf
ER -