Bounding the k-rainbow total domination number

被引:5
作者
Ojakian, Kerry [1 ]
Skrekovski, Riste [2 ,3 ]
Tepeh, Aleksandra [3 ,4 ]
机构
[1] CUNY, Bronx Community Coll, Dept Math & Comp Sci, Bronx, NY 10453 USA
[2] Univ Ljubljana, FMF, Ljubljana 1000, Slovenia
[3] Fac Informat Studies, Novo Mesto 8000, Slovenia
[4] Univ Maribor, FERI, Maribor 2000, Slovenia
关键词
Graph theory; Domination; Total domination; Rainbow domination; Vizing's conjecture; 2-RAINBOW DOMINATION; PRODUCT;
D O I
10.1016/j.disc.2021.112425
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let [k] ={1, 2,..., k}, where the elements of [k] are called colors. Supposing f is a function which assigns a subset of [k] to each vertex of a graph G, if each vertex which is assigned the empty set has all k colors in its neighborhood, then fis called a k-rainbow dominating function for G. If f satisfies the additional condition that for every v is an element of V(G) such that f( v) ={i} for some i is an element of[k] there exists u is an element of N-G(v) such that i is an element of f(u), then fis called a k-rainbow total dominating function. The corresponding invariant gamma(krt)(G), which is the minimum sum of numbers of assigned colors over all vertices of G, is called the k-rainbow total domination number of G. We present bounds on this domination invariant in terms of domination, total domination, and k-rainbow (total) domination. We compute gamma(krt)(K-a,K-b), and use this result in a number of places. We establish that for k = 3, the following bounds are tight: gamma((k-1)rt)(G) <= gamma(krt)(G) <= k/k-1 gamma((k-1)rt)(G); we prove similar bounds related to rainbow domination and total domination. For a graph G, its ordinary domination number gamma(G), and k >= 2, we prove that gamma(krt)(G) >= 2k/k+1 gamma(G), which presents a generalization of a result for the case k = 2 by Goddard and Henning (2018); we then consider some implications of this result. We conclude the paper with Vizing-like conjectures for both rainbow domination and rainbow total domination, and relate the later one with the original Vizing conjecture. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:11
相关论文
共 23 条
  • [1] Azarija J, 2017, ELECTRON J COMB, V24
  • [2] Bresar B, 2008, TAIWAN J MATH, V12, P213
  • [3] On the 2-rainbow domination in graphs
    Bresar, Bostjan
    Sumenjak, Tadeja Kraner
    [J]. DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) : 2394 - 2400
  • [4] Vizing's conjecture: a survey and recent results
    Bresar, Bostjan
    Dorbec, Paul
    Goddard, Wayne
    Hartnell, Bert L.
    Henning, Michael A.
    Klavzar, Sandi
    Rall, Douglas F.
    [J]. JOURNAL OF GRAPH THEORY, 2012, 69 (01) : 46 - 76
  • [5] Brigham R.C., 2000, J COMBIN COMPUT COMB, V34, P81
  • [6] Rainbow domination on trees
    Chang, Gerard J.
    Wu, Jiaojiao
    Zhu, Xuding
    [J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (01) : 8 - 12
  • [7] Clark W.E., 2000, ELECTRON J COMB, V7
  • [8] TOTAL DOMINATION IN GRAPHS
    COCKAYNE, EJ
    DAWES, RM
    HEDETNIEMI, ST
    [J]. NETWORKS, 1980, 10 (03) : 211 - 219
  • [9] A note on domination and total domination in prisms
    Goddard, Wayne
    Henning, Michael A.
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (01) : 14 - 20
  • [10] Hartnell B, 1998, MG TXB PUR APPL MATH, V209, P163