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 等数据库收录! |
|