PDF
Discussiones Mathematicae Graph Theory 25(1-2) (2005)
51-56
DOI: https://doi.org/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, 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
Close