Domination numbers in graphs with removed edge or set of edges
Magdalena Lemańska
Discussiones Mathematicae Graph Theory, Tome 25 (2005), p. 51-56 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:270684 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1259,
     author = {Magdalena Lema\'nska},
     title = {Domination numbers in graphs with removed edge or set of edges},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {25},
     year = {2005},
     pages = {51-56},
     zbl = {1079.05068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1259}
}

Magdalena Lemańska. Domination numbers in graphs with removed edge or set of edges. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 51-56. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1259/

[000] [1] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc. 1998). | Zbl 0890.05002

[001] [2] J. Topp, Domination, independence and irredundance in graphs, Dissertationes Mathematicae 342 (PWN, Warszawa, 1995).