Italian Reinforcement Number in Graphs

Abstract

An Italian dominating function (IDF) on a graph G = (V, E) is a function f:V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1 under f. The weight of an IDF f is the value Σv∈Vf(v). The Italian domination number of a graph G is the minimum weight of an IDF on G. The Italian reinforcement number of a graph is the minimum number of edges that have to be added to the graph in order to decrease the Italian domination number. In this paper, we initiate the study of Italian reinforcement number and we present some sharp upper bounds for this parameter. In particular, we determine the exact Italian reinforcement numbers of some classes of graphs.

Keywords

• Italian domination number
• Italian reinforcement number
• Cartesian product