A New Upper Bound for the Perfect Italian Domination Number of a Tree

Abstract

A perfect Italian dominating function (PIDF) on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that for every vertex u with f(u) = 0, the total weight of f assigned to the neighbors of u is exactly two. The weight of a PIDF is the sum of its functions values over all vertices. The perfect Italian domination number of G, denoted γIp(G)\gamma _I^p\left( G \right), is the minimum weight of a PIDF of G. In this paper, we show that for every tree T of order n ≥ 3, with ℓ(T) leaves and s(T) support vertices, γpI(T) ≤ γIp(T)≤4n-l(T)+2s(T-1)5\gamma _I^p\left( T \right) \le {{4n - \mathcal{l}\left( T \right) + 2s\left( {T - 1} \right)} \over 5}, improving a previous bound given by T.W. Haynes and M.A. Henning in [Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177].

Keywords

• italian domination
• roman domination
• perfect italian domination
• 05c69