DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

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