Independent Rainbow Domination of Graphs
Tóm tắt
Given a positive integer t and a graph F, the goal is to assign a subset of the color set
$$\{1,2,\ldots ,t\}$$
to every vertex of F such that every vertex with the empty set assigned has all t colors in its neighborhood. Such an assignment is called the t-rainbow dominating function (
$$t\mathrm{RDF}$$
) of the graph F. A
$$t\mathrm{RDF}$$
is independent (
$$It\mathrm{RDF}$$
) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a
$$t\mathrm{RDF}$$
g of a graph F is the value
$$w(g) =\sum _{v \in V(F)}|g(v)|$$
. The independent t-rainbow domination number
$$i_{rt}(F)$$
is the minimum weight over all
$$It\mathrm{RDF}$$
s of F. In this article, it is proved that the independent t-rainbow domination problem is NP-complete even if the input graph is restricted to a bipartite graph or a planar graph, and the results of the study provide some bounds for the independent t-rainbow domination number of any graph for a positive integer t. Moreover, the exact values and bounds of the independent t-rainbow domination numbers of some Petersen graphs and torus graphs are given.
Tài liệu tham khảo
Brešar, B., Henning, M.A., Rall, D.F.: Paired-domination of Cartesian products of graphs and rainbow domination. Electron. Notes Discrete Math. 22, 233–237 (2005)
Brešar, B., Henning, M.A., Rall, D.F.: Rainbow domination in graphs. Taiwan. J. Math. 12(1), 213–225 (2008)
Brešar, B., Šumenjak, T.K.: On the 2-rainbow domination in graphs. Discrete Appl. Math. 155(1), 2394–2400 (2007)
Chang, G.J., Wu, J., Zhu, X.: Rainbow domination on trees. Discrete Appl. Math. 158, 8–12 (2010)
Chen, W., Lu, Z., Wu, W.: Dominating problems in swapped networks. Inf. Sci. 269, 286–299 (2014)
Ebrahimi, B.J., Jahanbakht, N., Mahmoodianc, E.S.: Vertex domination of generalized Petersen graphs. Discrete Math. 309, 4355–4361 (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, San Francisco (1979)
Goddard, W., Henning, M.A.: Independent domination in graphs: a survey and recent results. Discrete Math. 313(7), 839–854 (2013)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
Kelleher, L.L., Cozzens, M.B.: Dominating sets in social network graphs. Math. Soc. Sci. 16(3), 267–279 (1988)
Klavžar, S., Žerovnik, J.: Algebraic approach to fasciagraphs and rotagraphs. Discrete Appl. Math. 68, 93–100 (1996)
Šumenjak, T.K., Rall, D.F., Tepeh, A.: Rainbow domination in the lexicographic product of graphs. arXiv:1210.0514v2. 13 Mar 2013
Ore, O.: Theory of Graphs. American Mathematical Society, Providence (1967)
Pang, C., Zhang, R., Zhang, Q., Wang, J.: Dominating sets in directed graphs. Inf. Sci. 180(19), 3647–3652 (2010)
Pavlič, P., Žerovnik, J.: Roman domination number of the Cartesian products of paths and cycles. Electron. J. Comb. 16, P19 (2012)
Pavlič, P., Žerovnik, J.: A note on the domination number of the cartesian products of paths and cycles. Kragujev. J. Math. 37, 275–285 (2013)
Pavlič, P., Žerovnik, J.: Formulas for various domination numbers of products of paths and cycles. Ars combinatoria, accepted for publication. preprint 1180 (2012). http://preprinti.imfm.si
Shao, Z., Zhu, E., Lang, F.: On the domination number of Cartesian product of two directed cycles. J. Appl. Math. (2013), Article ID 619695
Shao, Z., Liang, M., Yin, C., Xu, X., Pavlič, P., Žerovnik, J.: On rainbow domination numbers of graphs. Inf. Sci. 254, 225–234 (2014)
Steimle, A., Staton, W.: The isomorphism classes of the generalized Petersen graphs. Discrete Math. 309, 231–237 (2009)
Tong, C., Lin, X., Yang, Y., Luo, M.: 2-rainbow domination of generalized Petersen graphs \(P(n, 2)\). Discrete Appl. Math. 157, 1932–1937 (2009)
Tsai, Y., Lin, Y., Hsu, F.R.: Efficient algorithms for the minimum connected domination on trapezoid graphs. Inf. Sci. 177(12), 2405–2417 (2007)
Watkins, M.: A theorem on Tait colorings with an application to the generalized Petersen graph. J. Comb. Theory 6, 152–164 (1969)
Wu, L., Shan, E., Liu, Z.: On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs. Inf. Sci. 180(22), 4430–4435 (2010)
Xu, G.: 2-rainbow domination in generalized Petersen graphs \(P(n, 3)\). Discrete Appl. Math. 157, 2570–2573 (2009)
Yen, W.: The bottleneck independent domination on the classes of bipartite graphs and block graphs. Inf. Sci. 157, 199–215 (2003)
Žerovnik, J.: Deriving formulas for domination numbers of fasciagraphs and rotagraphs. Lect. Notes Comput. Sci. 1684, 559–568 (1999)