Discussiones Mathematicae Graph Theory 25(12) (2005)
5156
doi: 10.7151/dmgt.1259
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, 80952 Gdańsk, Poland
email: 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−E_{p}) ≤
γ_{w}(G)+p−1
and γ_{c}(G) ≤
γ_{c}(G−E_{p})
≤
γ_{c}(G)+2p−2
if G and G−E_{p} are
connected and E_{p} = E(H_{p}) where H_{p} 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