Let $ f:V(G)\rightarrow \{0, 1, 2\} $ be a function defined from a connected graph $ G $. Let $ W_i = \{x\in V(G): f(x) = i\} $ for every $ i\in \{0, 1, 2\} $. The function $ f $ is called a total Italian dominating function on $ G $ if $ \sum_{v\in N(x)}f(v)\geq 2 $ for every vertex $ x\in W_0 $ and if $ \sum_{v\in N(x)}f(v)\geq 1 $ for every vertex $ x\in W_1\cup W_2 $. The total Italian domination number of $ G $, denoted by $ \gamma_{tI}(G) $, is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all total Italian dominating functions $ f $ on $ G $. In this paper, we provide new lower and upper bounds on the total Italian domination number of trees. In particular, we show that if $ T $ is a tree of order $ n(T)\geq 2 $, then the following inequality chains are satisfied.
(ⅰ) $ 2\gamma(T)\leq \gamma_{tI}(T)\leq n(T)-\gamma(T)+s(T) $,
(ⅱ) $ \frac{n(T)+\gamma(T)+s(T)-l(T)+1}{2}\leq \gamma_{tI}(T)\leq \frac{n(T)+\gamma(T)+l(T)}{2}, $
where $ \gamma(T) $, $ s(T) $ and $ l(T) $ represent the classical domination number, the number of support vertices and the number of leaves of $ T $, respectively. The upper bounds are derived from results obtained for the double domination number of a tree.
Citation: Abel Cabrera-Martínez, Andrea Conchado Peiró, Juan Manuel Rueda-Vázquez. Further results on the total Italian domination number of trees[J]. AIMS Mathematics, 2023, 8(5): 10654-10664. doi: 10.3934/math.2023540
Let $ f:V(G)\rightarrow \{0, 1, 2\} $ be a function defined from a connected graph $ G $. Let $ W_i = \{x\in V(G): f(x) = i\} $ for every $ i\in \{0, 1, 2\} $. The function $ f $ is called a total Italian dominating function on $ G $ if $ \sum_{v\in N(x)}f(v)\geq 2 $ for every vertex $ x\in W_0 $ and if $ \sum_{v\in N(x)}f(v)\geq 1 $ for every vertex $ x\in W_1\cup W_2 $. The total Italian domination number of $ G $, denoted by $ \gamma_{tI}(G) $, is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all total Italian dominating functions $ f $ on $ G $. In this paper, we provide new lower and upper bounds on the total Italian domination number of trees. In particular, we show that if $ T $ is a tree of order $ n(T)\geq 2 $, then the following inequality chains are satisfied.
(ⅰ) $ 2\gamma(T)\leq \gamma_{tI}(T)\leq n(T)-\gamma(T)+s(T) $,
(ⅱ) $ \frac{n(T)+\gamma(T)+s(T)-l(T)+1}{2}\leq \gamma_{tI}(T)\leq \frac{n(T)+\gamma(T)+l(T)}{2}, $
where $ \gamma(T) $, $ s(T) $ and $ l(T) $ represent the classical domination number, the number of support vertices and the number of leaves of $ T $, respectively. The upper bounds are derived from results obtained for the double domination number of a tree.
| [1] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998. |
| [2] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs: Advanced topics, Chapman & Hall/CRC Pure and Applied Mathematics, Taylor & Francis, 1998. |
| [3] |
S. C. García, A. Cabrera-Martínez, F. A. Hernández Mira, I. G. Yero, Total Roman $\{2\}$-domination in graphs, Quaest. Math., 44 (2022), 411–434. https://doi.org/10.2989/16073606.2019.1695230 doi: 10.2989/16073606.2019.1695230
|
| [4] |
H. A. Ahangar, M. Chellali, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro, Total Roman $\{2\}$-dominating functions in graphs, Discuss. Math. Graph Theory, 42 (2022), 937–958. https://doi.org/10.7151/dmgt.2316 doi: 10.7151/dmgt.2316
|
| [5] |
H. Abdollahzadeh Ahangar, M. Chellali, M. Hajjari, S. M. Sheikholeslami, Further progress on the total Roman $\{2\}$-domination number of graphs, Bull. Iranian Math. Soc., 48 (2022), 1111–1119. https://doi.org/10.1007/s41980-021-00565-z doi: 10.1007/s41980-021-00565-z
|
| [6] |
A. Cabrera-Martínez, S. C. García, J. A. Rodríguez-Velázquez, Double domination in lexicographic product graphs, Discrete Appl. Math., 284 (2020), 290–300. https://doi.org/10.1016/j.dam.2020.03.045 doi: 10.1016/j.dam.2020.03.045
|
| [7] |
P. Chakradhar, P. V. S. Reddy, Algorithmic aspects of total Roman $\{2\}$-domination in graphs, Commun. Comb. Optim., 7 (2022), 183–192. https://doi.org/10.22049/CCO.2021.27063.1189 doi: 10.22049/CCO.2021.27063.1189
|
| [8] |
S. M. Sheikholeslami, L. Volkmann, Nordhaus-Gaddum type inequalities on the total Italian domination number in graphs, RAIRO Oper. Res., 56 (2022), 2235–2243. https://doi.org/10.1051/ro/2022108 doi: 10.1051/ro/2022108
|
| [9] | F. Harary, T. W. Haynes, Double domination in graphs, Ars Combin., 55 (2000), 201–213. |
| [10] |
A. Cabrera-Martínez, New bounds on the double domination number of trees, Discrete Appl. Math., 315 (2022), 97–103. https://doi.org/10.1016/j.dam.2022.03.022 doi: 10.1016/j.dam.2022.03.022
|
| [11] |
A. Cabrera-Martínez, Some new results on the $k$-tuple domination number of graphs, RAIRO Oper. Res., 56 (2022), 3491–3497. https://doi.org/10.1051/ro/2022159 doi: 10.1051/ro/2022159
|
| [12] |
A. Cabrera-Martínez, J. A. Rodríguez-Velázquez, A note on double domination in graphs, Discrete Appl. Math., 300 (2021), 107–111. https://doi.org/10.1016/j.dam.2021.05.011 doi: 10.1016/j.dam.2021.05.011
|
| [13] |
M. Hajian, N. J. Rad, A new lower bound on the double domination number of a graph, Discrete Appl. Math., 254 (2019), 280–282. https://doi.org/10.1016/j.dam.2018.06.009 doi: 10.1016/j.dam.2018.06.009
|
| [14] |
N. A. A. Aziz, N. J. Rad, H. Kamarulhaili, A note on the double domination number in maximal outerplanar and planar graphs, RAIRO Oper. Res., 56 (2022), 3367–3371. https://doi.org/10.1051/ro/2022150 doi: 10.1051/ro/2022150
|
| [15] | A. Meir, J. W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math., 61 (1975), 225–233. |
| [16] |
A. Cabrera-Martínez, A. C. Peiró, On the $\{2\}$-domination number of graphs. AIMS Math., 7 (2022), 10731–10743. https://doi.org/10.3934/math.2022599 doi: 10.3934/math.2022599
|
| [17] |
M. Lemanska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory, 24 (2004), 165–169. https://doi.org/10.7151/dmgt.1222 doi: 10.7151/dmgt.1222
|
Figures(1)
Abel Cabrera-Martínez, Andrea Conchado Peiró, Juan Manuel Rueda-Vázquez. Further results on the total Italian domination number of trees[J]. AIMS Mathematics, 2023, 8(5): 10654-10664. doi: 10.3934/math.2023540
DownLoad: