DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

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