Samodivkin, V. (2016). Hypo-efficient domination and hypo-unique domination. Communications in Combinatorics and Optimization, 1(2), 103-116. doi: 10.22049/cco.2016.13553

Vladimir Samodivkin. "Hypo-efficient domination and hypo-unique domination". Communications in Combinatorics and Optimization, 1, 2, 2016, 103-116. doi: 10.22049/cco.2016.13553

Samodivkin, V. (2016). 'Hypo-efficient domination and hypo-unique domination', Communications in Combinatorics and Optimization, 1(2), pp. 103-116. doi: 10.22049/cco.2016.13553

Samodivkin, V. Hypo-efficient domination and hypo-unique domination. Communications in Combinatorics and Optimization, 2016; 1(2): 103-116. doi: 10.22049/cco.2016.13553

Hypo-efficient domination and hypo-unique domination

^{}University of Architecture, Civil Đ•ngineering and Geodesy; Department of Mathematics

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 $vin 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.