Outer independent rainbow dominating functions in graphs

• Autorzy: Mansouri Zhila , Mojdeh Doost Ali

Identyfikatory

DOI

10.7494/OpMath.2020.40.5.599

• Języki publikacji: EN

Abstrakty

EN

A 2-rainbow dominating function (2-rD function) of a graph G = (V, E) is a function ƒ: V(G) → {0, {1}, {2}, {1, 2}} having the property that if ƒ (x) = 0, then ƒ: (N(x)) = {1, 2}. The 2-rainbow domination number [formula] is the minimum weight of [formula] taken over all 2-rainbow dominating functions ƒ An outer-independent 2-rainbow dominating function (OI2-rD function) of a graph G is a 2-rD function ƒ for which the set of all v isin; V(G) with fnof; (v) = 0 is independent. The outer independent 2-rainbow domination number [formula] is the minimum weight of an OI2-rD function of G. In this paper, we study the OI2-rD number of graphs. We give the complexity of the problem OI2-rD of graphs and present lower and upper bounds on [formula ≤. Moreover, we characterize graphs with some small or large OI2-rD numbers and we also bound this parameter from above for trees in terms of the order, leaves and the number of support vertices and characterize all trees attaining the bound. Finally, we show that any ordered pair (a, b) is realizable as the vertex cover number and OI2-rD numbers of some non-trivial tree if and only if a + 1 ≤ b ≤ 2a.

Słowa kluczowe

EN

outer-independent rainbow domination; K1; r -free graphs; trees

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2020
• Tom: Vol. 40, no. 5
• Strony: 599--615
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Mansouri Zhila

• University of Mazandaran Department of Mathematics Babolsar, Iran

autor

Mojdeh Doost Ali

• University of Mazandaran Department of Mathematics Babolsar, Iran

Bibliografia

• [1] B. Bresar, M. Henning, D. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), 213-225.
• [2] B. Bresar, T.K. Sumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), 2394-2400.
• [3] G. Chang, J. Wu, X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010), 8-12.
• [4] T. Gallai, Uber extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eotvos Sect. Math. 2 (1959), 133-138.
• [5] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman & Co., New York, USA, 1979.
• [6] G. Hao, D.A. Mojdeh, S. Wei, Z. Xie, Rainbow domination in the Cartesian product of directed paths, Australas. J. Combin. 70 (2018), 349-361.
• [7] Q. Kang, V. Samodivkin, Z. Shao, S.M. Sheikholeslami, M. Soroudi, Outer-independent k-rainbow domination, J. Taibah. Univ. Sci. 13 (2019), 883-891.
• [8] Zh. Mansouri, D.A. Mojdeh, Rainbow and independent rainbow domination of graphs, submitted.
• [9] D.A. Mojdeh, Zh. Mansouri, On the independent double roman domination in graphs, Bull. Iran. Math. Soc. (2019), https://doi.org/10.1007/s41980-019-00300-9.
• [10] D.A. Mojdeh, A. Parsian, I. Masoumi, Characterization of double Roman trees, Ars Combin., to appear.
• [11] D.B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, USA, 2001.
• [12] Y. Wu, N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs and Combin. 29 (2013), 1125-1133.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).