Triple Roman domination subdivision number in graphs (Q6046760)
From MaRDI portal
scientific article; zbMATH DE number 7734843
Language | Label | Description | Also known as |
---|---|---|---|
English | Triple Roman domination subdivision number in graphs |
scientific article; zbMATH DE number 7734843 |
Statements
Triple Roman domination subdivision number in graphs (English)
0 references
6 September 2023
0 references
For a graph \(G=(V,E)\), a function \(f:V(G)\mapsto \{0,1,2,3,4\}\) is called a triple Roman domination function if \(f(AN[v])\geq |AN(v)|+3\) for any \(v\in V(G)\) with \(f(v)<3\), where \(AN(v)=\{w\in N(v)|\ f(w)\geq 1\}\) and \(AN[v]=AN(v)\cup\{v\}\). Let \(\omega(f)=\sum_{v\in V} f(v)\). The triple Roman domination number, denoted by \(\gamma_{[3R]}(G)\), is the \(\min\{\omega(f): f \text{ is a triple Roman domination function on }G\}\). The triple Roman domination subdivision number \(sd_{[3R]}(G)\) of a graph \(G\) is the minimum number of edges that must be subdivided (each edge in \(G\) can be subdivided at most once) to increase the triple Roman domination number. In the paper, the authors show that the decision problem associated with \(sd_{[3R]}(G)\) is NP-hard, and establish upper bounds on \(sd_{[3R]}(G)\) for a general graph \(G\).
0 references
triple Roman domination number
0 references
triple Roman domination subdivision number
0 references