Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Opuscula Mathematica

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: total domination number

Sortuj według:

Ogranicz wyniki do:

Bounds on the 2-domination number in cactus graphs

Chellali M.

Opuscula Mathematica

2006

Vol. 26, no. 1

5-12

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in S is dominated at least twice. The minimum cardinality of a 2-dominating set of G is the 2-domination number γ2(G). We show that if G is a nontrivial connected cactus graph with k(G) even cycles (k(G) ≥ 0), then γ2(G) ≥ γt(G) - k(G), and if G is a graph of order n with at most one cycle, then γ2(G) ≥ (n + l - s)/2 improving Fink and Jacobson's lower bound for trees with l > s, where γt(G), l and s are the total domination number, the number of leaves and support vertices of G, respectively. We also show that if T is a tree of order n ≥ 3, then γ2(T) ≤ β(T) + s - 1, where β(T) is the independence number of T.

Domination parameters of a graph with added vertex

Zwierzchowski M.

Opuscula Mathematica

2004

Vol. 24, no. 2

231-234

Let G = (V, E) be a graph. A subset D ⊆ V is a total dominating set of G if for every vertex y ∈ V there is a vertex x ∈ D with xy ∈ E. A subset D ⊆ V is a strong dominating set of G if for every vertex y ∈ V - D there is a vertex x ∈ D with xy &isin E and degG(x) ≥ degG(y). The total domination number γt(G) (the strong domination number γS(G)) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of G. The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [1], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [3]. By a subdivision of an edge uv ∈ E we mean removing edge uv, adding a new vertex x, and adding edges ux and vx. A graph obtained from G by subdivision an edge uv ∈ E is denoted by G ⊕ uxvx. The behaviour of the total domination number and the strong domination number of a graph G ⊕ uxvx is developed.