Bounds on the 2-domination number in cactus graphs

• Autorzy: Chellali M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

2-domination number; total domination number; independence number; cactus graphs; trees

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2006
• Tom: Vol. 26, no. 1
• Strony: 5--12
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Chellali M.

• University of Blida, Department of Mathematics, B.P. 270, Blida, Algeria,

Bibliografia

• [1] Blidia M., Chellali M., Favaron O., Independence and 2-domination in trees. Australasian J. Comb. 33 (2005), 317-327.
• [2] Blidia M., Chellali M., Volkmann L., Bounds of the 2-domination number of graphs Utilitas Math., to appear.
• [3] Favaron O., On a conjecture of Fink and Jacobson concerning k-domination and k-dependence. J. Combinat. Theory Ser. B 39 (1985), 101-102.
• [4] Favaron O. A bound on the independent domination number of a tree, Int. J. Graph Theory 1(1) (1992), 19-27.
• [5] Fink J. F., Jacobson M. S., n-domination in graphs, in: Alavi Y. and Schwenk A. J. (eds), Graph Theory with Applications to Algorithms and Computer Science, New York, Wiley, 1985, 283-300.
• [6] Fink J.F., Jacobson M. S., On n-domination, n-dependence and forbidden sub-graphs. Graph Theory with Applications to Algorithms and Computer Science. New York, Wiley, 1985, 301-312.
• [7] Haynes T. W., Hedetniemi S. T., Henning M.A., Slater P. J., H-forming sets in graphs, Discrete Mathematics 262 (2003), 159-169.
• [8] Haynes T. W., Hedetniemi S.T., Slater P. J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [9] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.