>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved