On the Total Version of Triple Roman Domination in Graphs

Abstract

In this paper, we initiate the study of total triple Roman domination, in which we aim to ensure that each vertex of the graph is protected by at least three units, either located on itself or its neighbors, while guaranteeing that none of its neighbors remain unprotected. Formally, a total triple Roman dominating function is a labeling f of the vertices of the graph with labels {0,1,…,4} such that f(N[v])≥|AN(v)|+3, where AN(v) denotes the set of active neighbors of vertex v, i.e., those assigned a positive label. We investigate the algorithmic complexity of the associated decision problem, establish sharp bounds regarding graph structural parameters, and obtain the exact values for several graph families.