Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: connected domination number

Sortuj według:

Ogranicz wyniki do:

On the doubly connected domination number of a graph

100%

Cyman J., Lemańska M., Raczek J.

Open Mathematics

2006

tom 4

nr 1

34-45

For a given connected graph G = (V, E), a set $$D \subseteq V(G)$$ is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Domination numbers in graphs with removed edge or set of edges

100%

Lemańska M.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 1-2

51-56

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Open Mathematics

2 Lemańska M.

1 Cyman J.

1 Raczek J.

1 2006

1 2005

Wyniki wyszukiwania

On the doubly connected domination number of a graph

Domination numbers in graphs with removed edge or set of edges