Page 1

Displaying 1 – 9 of 9

Showing per page

Domination numbers in graphs with removed edge or set of edges

Magdalena Lemańska (2005)

Discussiones Mathematicae Graph Theory

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 ) + 2 p - 2 if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected...

Currently displaying 1 – 9 of 9

Page 1