Geodesic
Domination numbers in graphs with removed edge or set of edges
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 51-56 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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ₚ) ≤ γ_w(G) + p - 1 and γ_c(G) ≤ γ_c(G -Eₚ) ≤ γ_c(G) + 2p - 2 if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected subgraph of G.
Keywords: connected domination number, weakly connected domination number, edge removal 
@article{DMGT_2005_25_1-2_a5,
     author = {Lema\'nska, Magdalena},
     title = {Domination numbers in graphs with removed edge or set of edges},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {51--56},
     year = {2005},
     volume = {25},
     number = {1-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a5/}
}
TY  - JOUR
AU  - Lemańska, Magdalena
TI  - Domination numbers in graphs with removed edge or set of edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 51
EP  - 56
VL  - 25
IS  - 1-2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a5/
LA  - en
ID  - DMGT_2005_25_1-2_a5
ER  - 
%0 Journal Article
%A Lemańska, Magdalena
%T Domination numbers in graphs with removed edge or set of edges
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 51-56
%V 25
%N 1-2
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a5/
%G en
%F DMGT_2005_25_1-2_a5
Lemańska, Magdalena. Domination numbers in graphs with removed edge or set of edges. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 51-56. http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a5/

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