A note on a relation between the weak and strong domination numbers of a graph

• Autorzy: Boutrig R. , Chellali M.
• Języki publikacji: EN

Abstrakty

EN

In a graph G = (V, E) a vertex is said to dominate itself and all its neighbors. A set D ⊆ V is a weak (strong, respectively) dominating set of G if every vertex v ∈ V - S is adjacent to a vertex u ∈ D such that dG(v) ≥ dG(u) (dG(v) ≤ dG(u), respectively). The weak (strong, respectively) domination number of G, denoted by ϒw(G) (ϒs(G), respectively), is the minimum cardinality of a weak (strong, respectively) dominating set of G. In this note we show that if G is a connected graph of order n ≥ 3, then ϒw(G) + tϒs(G) ≤ n, where t = 3/(Δ+1) if G is an arbitrary graph, t = 3/5 if G is a block graph, and t = 2/3 if G is a claw free graph.

Słowa kluczowe

EN

weak domination; strong domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 2
• Strony: 235--238
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Boutrig R.

autor

Chellali M.

• University of Blida LAMDA-RO Laboratory, Department of Mathematics B.P. 270, Blida, Algeria,

Bibliografia

• [1] J.H. Hattingh, M.A. Henning, On strong domination in graphs, J. Combin. Math. Combin. Comput. 26 (1998) 73–92.
• [2] J.H. Hattingh, R.C. Laskar, On weak domination in graphs, Ars Combinatoria 49 (1998).
• [3] D. Rautenbach, Bounds on the weak domination number, Austral. J. Combin. 18 (1998), 245–251.
• [4] D. Rautenbach, Bounds on the strong domination number, Discrete Math. 215 (2000), 201–212.
• [5] E. Sampathkumar, L. Pushpa Latha, Strong, weak domination and domination balance in graphs, Discrete Math. 161 (1996), 235–242.