Discussiones Mathematicae Graph Theory 25(1-2) (2005)
DOMINATION NUMBERS IN GRAPHS WITH REMOVED EDGE OR SET OF EDGES
Department of Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
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)+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) ≤
and γc(G) ≤
if G and G−e
are connected. Additionally we show that γw(G)
and γc(G) ≤
if G and G−Ep are
connected and Ep = E(Hp) where Hp of order p is a connected
subgraph of G.
connected domination number, weakly connected domination number, edge removal.
2000 Mathematics Subject Classification: Primary: 05C69;
Secondary: 05C05, 05C85.
||| 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).
Received 28 October 2003
Revised 18 May 2004