A lower bound on the double outer-independent domination number of a tree

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

Abstrakty

EN

A vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V (G) \ D is independent. The double outer-independent domination number of a graph G, denoted by (…) (G), is the minimum cardinality of a double outer-independent dominating set of G. We prove that for every nontrivial tree T of order n, with l leaves and s support vertices we have (…) (T) _ (2n+l .s +2)/3, and we characterize the trees attaining this lower bound. We also give a constructive characterization of trees T such that(…) (T) = (2n + 2)/3.

Słowa kluczowe

EN

double outer-independent domination; double domination; tree

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2012
• Tom: Vol. 45, nr 1
• Strony: 17--23
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Krzykowski M.

• Faculty Of Electronics, Telecommunications And Informatics Gdańsk University Of Technology Narutowicza 11/12 80 -233 Gdańsk, Poland,

Bibliografia

• [1] M. Blidia, M. Chellali, O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005), 317–327.
• [2] M. Chellali, T. Haynes, A note on the total domination number of a tree, J. Combin. Math. Combin. Comput. 58 (2006), 189–193.
• [3] F. Harary, T. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213.
• [4] T. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [5] T. Haynes, S. Hedetniemi, P. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [6] M. Krzywkowski, Double outer-independent domination in graphs, submitted.