ArticleOriginal scientific text

Title

Domination numbers in graphs with removed edge or set of edges

Authors 1

Affiliations

  1. 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 γw and the connected domination number γc, i.e., we show that γw(G)γw(G-e)γw(G)+1 and γc(G)γc(G-e)γc(G)+2 if G and G-e are connected. Additionally we show that γw(G)γw(G-E)γw(G)+p-1 and γc(G)γc(G-E)γc(G)+2p-2 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

  1. T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc. 1998).
  2. J. Topp, Domination, independence and irredundance in graphs, Dissertationes Mathematicae 342 (PWN, Warszawa, 1995).
Pages:
51-56
Main language of publication
English
Received
2003-10-28
Accepted
2004-05-18
Published
2005
Exact and natural sciences