|
|
|
|
hypo-efficient domination and hypo-unique domination
|
|
|
|
|
|
|
|
نویسنده
|
samodivkin vladimir
|
|
منبع
|
communications in combinatorics and optimization - 2016 - دوره : 1 - شماره : 2 - صفحه:103 -116
|
|
چکیده
|
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.
|
|
کلیدواژه
|
domination number ,efficient domination ,unique domination ,hypo-property
|
|
آدرس
|
university of architecture, civil еngineering and geodesy, department of mathematics, bulgaria
|
|
پست الکترونیکی
|
vl.samodivkin@gmail.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|