Hypo-efficient domination and hypo-unique domination

Abstract

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.

Keywords

• domination number‎
• ‎efficient domination‎
• ‎unique domination‎
• ‎hypo-property.