ArticleOriginal scientific text
Title
Domination numbers in graphs with removed edge or set of edges
Authors 1
Affiliations
- Department of Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland
Abstract
It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number and the connected domination number , i.e., we show that and if G and G-e are connected. Additionally we show that and if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected subgraph of G.
Keywords
connected domination number, weakly connected domination number, edge removal
Bibliography
- T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc. 1998).
- J. Topp, Domination, independence and irredundance in graphs, Dissertationes Mathematicae 342 (PWN, Warszawa, 1995).