From the strong differential to Italian domination in graphs (Q2238746): Difference between revisions

Let \(G\) be a graph and let \(D\subseteq V(G)\). The external neighborhood \(N_e(D)\) of \(D\) contains all vertices outside of \(D\) that are adjacent to some vertex of \(D\). A vertex \(u\) is external private neighbor of \(v\in D\) if \(u\) is an external neighborhood of \(D\) and \(v\) is the only neighbor of \(u\) in \(D\). The set \(D_w\subseteq D\) contains all vertices from \(D\) that have an external private neighbor. The strong differential \(\partial_s(D)\) of set \(D\) then equals to \(|N_e(D)|-|D_w|\) and the strong differential \(\partial_s(G)\) of \(G\) is maximum of strong differentials \(\partial_s(D)\) over all sets \(D\subseteq V(G)\). Partition \((V_0,V_1,V_2)\) of \(V(G)\) is an Italian partition of \(G\) if every vertex from \(V_0\) has a neighbor in \(V_2\) or two neighbors in \(V_1\). The weight of this partition is \(f(V_0,V_1,V_2)=|V_1|+2|V_2|\). The Italian domination number \(\gamma_I(G)\) is then the minimum weight \(f(V_0,V_1,V_2)\) over all Italian partitions \((V_0,V_1,V_2)\). This is an introductory work on the strong differential \(\partial_s(G)\) of a graph \(G\). The most important is the Gallai-type formula for a strong differential of a graph and Italian domination number, that is \[\partial_s(G)+\gamma_I(G)=|V(G)|.\] Hence, one can study Italian domination over the strong differential of a graph. Also several bounds are presented for \(\partial_s(G)\) with respect to the order, maximum degree, domination number, differential of a graph and some others.