Algorithmic aspect on total Roman {2}-domination of Cartesian products of paths and cycles

College of Science, China Jiliang University, Hangzhou 310018, P.R. China

^* Corresponding author: chenqin0308@126.com

Received: 28 December 2022
Accepted: 21 August 2023

Abstract

A total Roman {2}-dominating function (TR2DF) on a graph G with vertex set V is a function f : V → {0, 1, 2} having the property that for every vertex v with f(v) = 0, ∑_{u∈N (v)} f(u) ≥ 2, where N(v) represents the open neighborhood of v, and the subgraph of G induced by the set of vertices with f(v) > 0 has no isolated vertex. The weight of a TR2DF f is the value w(f) = ∑_v∈V f(v), and the minimum weight of a TR2DF of G is the total Roman {2}-domination number γ_tR2(G). The total Roman {2}-domination problem (TR2DP) is to determine the value γ_tR2(G). In this paper, we first propose an integer linear programming (ILP) formulation for the TR2DP. Furthermore, we apply the discharging approach to determine the total Roman {2}-domination number for some Cartesian products of paths and cycles.