Domination numbers in graphs with removed edge or set of edges

• Autorzy: Magdalena Lemańska
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

connected domination number; weakly connected domination number; edge removal

Kategorie tematyczne

• 05C05: Trees
• 05C69: Dominating sets, independent sets, cliques
• 05C85: Graph algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 1-2
• Strony: 51-56

Daty

wydano

2005

otrzymano

2003-10-28

poprawiono

2004-05-18

Twórcy

autor

Magdalena Lemańska

• Department of Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1259