首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Changing and unchanging of the domination number of a graph
Authors:Vladimir Samodivkin  
Institution:aDepartment of Mathematics, University of Architecture, Civil Engineering and Geodesy, Hristo Smirnenski Blv. 1, 1046 Sofia, Bulgaria
Abstract:Let G be a graph and γ(G) denote the domination number of G. A dominating set D of a graph G with |D|=γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-fixed if x belongs to every γ-set, (ii) γ-free if x belongs to some γ-set but not to all γ-sets, (iii) γ-bad if x belongs to no γ-set, (iv) γ--free if x is γ-free and γ(G-x)=γ(G)-1, (v) γ0-free if x is γ-free and γ(G-x)=γ(G), and (vi) γq-fixed if x is γ-fixed and γ(G-x)=γ(G)+q. In this paper we investigate for any vertex x of a graph G whether x is γq-fixed, γ0-free, γ--free or γ-bad when G is modified by deleting a vertex or adding or deleting an edge.
Keywords:Domination number  Cut-vertex  Tree  Bridge
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号