# Domination numbers in graphs with removed edge or set of edges

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 1-2, page 51-56
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMagdalena Lemańska. "Domination numbers in graphs with removed edge or set of edges." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 51-56. <http://eudml.org/doc/270684>.

@article{MagdalenaLemańska2005,

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-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.},

author = {Magdalena Lemańska},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {connected domination number; weakly connected domination number; edge removal},

language = {eng},

number = {1-2},

pages = {51-56},

title = {Domination numbers in graphs with removed edge or set of edges},

url = {http://eudml.org/doc/270684},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Magdalena Lemańska

TI - Domination numbers in graphs with removed edge or set of edges

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 1-2

SP - 51

EP - 56

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

LA - eng

KW - connected domination number; weakly connected domination number; edge removal

UR - http://eudml.org/doc/270684

ER -

## References

top- [1] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc. 1998). Zbl0890.05002
- [2] J. Topp, Domination, independence and irredundance in graphs, Dissertationes Mathematicae 342 (PWN, Warszawa, 1995).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.