Generous Roman Domination Subdivision Number in Graph

European Journal of Pure and Applied Mathematics, vol. 18, pp. 6429

Abstract

Let $G = (V, E)$ be a simple graph, and let $f: V \to \{0, 1, 2, 3\}$ be a function. A vertex \( u \) is considered an undefended vertex with respect to \( f \) if \( f(u) = 0 \) and there is no adjacent vertex \( v \) satisfying \( f(v) \geq 2 \). A function \( f \) is termed a generous Roman dominating function (GRD-function) if, for every vertex \( u \) with \( f(u) = 0 \), there exists at least one adjacent vertex \( v \) such that \( f(v) \geq 2 \) and the modified function \( f': V \to \{0,1,2,3\} \), defined as\( f'(u) = \alpha, \quad f'(v) = f(v) - \alpha,\) where \( \alpha \in \{1,2\} \), and\(f'(w) = f(w) \quad \text{for all } w \in V \setminus \{u, v\},\) ensures that no vertex remains undefended. The weight of a GRD-function \( f \) is defined as\(f(V) = \sum_{u \in V} f(u).\) The smallest possible weight of a GRD-function on \( G \) is known as the generous Roman domination number of \( G \), denoted by \( \gamma_{gR}(G) \). The generous Roman domination subdivision number, represented as \( \mathrm{sd}_{\gamma_{gR}}(G) \), is the minimum number of edges that must be subdivided (where each edge in \( G \) can be subdivided at most once) to increase the generous Roman domination number. In this paper, we establish upper bounds on the generous Roman domination subdivision number. Furthermore, we determine the exact value of this parameter for certain families of graphs, including paths, cycles, and ladders. Further, we present several sufficient conditions for a graph \( G \) to have a small value of \( sd_{\gamma_{gR}}(G) \).\end{abstract}\keywords{generous Roman domination, generous Roman domination subdivision number}

Authors 5

1. Jamil J. Hamja

   Mindanao State University - Tawi-Tawi College of Technology and Oceanography

   Affiliation as printed

   MSU-Tawi - Tawi College of Technology and Oceanography

2. Seyed Mahmoud Sheikholeslami

   Azarbaijan Shahid Madani University

   Affiliation as printed

   Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

3. Lutz Volkmann Aachen Lehrstuhl II f\"{u}r Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl II f\"{u}r Mathematik, RWTH Aachen University, 52056 Aachen, Germany

4. Imelda Aniversario

   Mindanao State University – Iligan Institute of Technology

   Affiliation as printed

   Department of Mathematics and Statistics, College of Science and Mathematics, MSU - Iligan Institute of Technology, 9200 Iligan City, Philippines

5. Lucille M. Bugo

   Mindanao State University – Iligan Institute of Technology

   Affiliation as printed

   Department of Mathematics and Statistics, College of Science and Mathematics, MSU - Iligan Institute of Technology, 9200 Iligan City, Philippines