Discussiones Mathematicae Graph Theory 25(1-2) (2005) 51-56
doi: 10.7151/dmgt.1259

[BIBTex] [PDF] [PS]

DOMINATION NUMBERS IN GRAPHS WITH REMOVED EDGE OR SET OF EDGES

Magdalena Lemańska

Department of Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: magda@mif.pg.gda.pl

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−Ep) ≤ γw(G)+p−1 and γc(G) ≤ γc(G−Ep) ≤ γc(G)+2p−2 if G and G−Ep are connected and Ep = E(Hp) where Hp of order p is a connected subgraph of G.

Keywords: connected domination number, weakly connected domination number, edge removal.

2000 Mathematics Subject Classification: Primary: 05C69;
Secondary: 05C05, 05C85.

References

[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).

Received 28 October 2003
Revised 18 May 2004