Title of article :
hypo-efficient domination and hypo-unique domination
Author/Authors :
samodivkin, vladimir university of architecture, civil еngineering and geodesy - department of mathematics, sofia, bulgaria
Abstract :
for a graph g let γ(g) be its domination number. we define a graph g to be (i) a hypo-efficient domination graph (or a hypo-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-ud graph) if g has at least two minimum dominating sets, but g−v has a unique minimum dominating set for each v∈v(g). we show that each hypo-ud graph g of order at least 3 is connected and γ(g−v) γ(g) for all v∈v. we obtain a tight upper bound on the order of a hypo-p graph in terms of the domination number and maximum degree of the graph, where p∈{ud,ed}. families of circulant graphs, which achieve these bounds, are presented. we also prove that the bondage number of any hypo-ud graph is not more than the minimum degree plus one.
Keywords :
domination number , efficient domination , unique domination , hypo , property
Journal title :
Communications in Combinatorics and Optimization
Journal title :
Communications in Combinatorics and Optimization