On equality in an upper bound for the acyclic domination number

• Autorzy: Samodivkin V.
• Języki publikacji: EN

Abstrakty

EN

A subset A of vertices in a graph G is acyclic if the subgraph it induces contains no cycles. The acyclic domination number ϒa (G) of a graph G is the minimum cardinality of an acyclic dominating set of G. For any graph G with n vertices and maximum degree Δ(G), ϒa(G) ≤ n - Δ(G). In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.

Słowa kluczowe

EN

dominating set; acyclic set; independent set; acyclic domination number

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2008
• Tom: Vol. 28, no. 3
• Strony: 331--334
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Samodivkin V.

• University of Architecture Civil Engineering and Geodesy, Department of Mathematics, Hristo Smirnenski 1 Blv., 1046 Sofia, Bulgaria,

Bibliografia

• [1] C. Berge, Theory of graphs and its application, Methuen, London, 1962.
• [2] Y. Chen, Y. Zhang, K. Zhang, Is γa(G) ≤ δ for graphs which have diameter two?, Journal of Systems Science and Complexity 16 (2003) 2, 195–198.
• [3] T.C.E. Cheng, Y. Chen, C.T. Ng, A note on acyclic domination number in graphs of diameter two, Discrete Mathematics 154 (2006), 1019–1022.
• [4] G.S. Domke, J.E. Dunbar, L.R. Markus, Gallai-type theorems and domination parameters, Discrete Mathematics 167/168 (1997), 237–248.
• [5] O. Favaron, C.M. Mynhardt, On equality in an upper bound for domination parameters of graphs, J. Graph Theory 24 (1997) 3, 221–231.
• [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in graphs, Marcel Dekker, Inc., New York, NY, 1998.
• [7] S. Hedetniemi, S.T. Hedetniemi, D. Rall, Acyclic domination, Discrete Mathematics 222 (2000), 151–165.
• [8] V.D. Samodivkin, Minimal acyclic dominating sets and cut-vertices, Mathematica Bohemica 120 (2005) 81–88.
• [9] V.D. Samodivkin, Changing and unchanging acyclic domination: edge addition, Australasian Journal of Combinatorics 38 (2007), 309–316.