Perfect triple Roman domination

DOI10.1016/J.DAM.2025.06.010MaRDI QIDQ6930353zbMATH OpenFDO

Authors M. Kor, J. Amjadi, Mustapha Chellali, Seyed Mahmood Sheikholeslami

Publication date 16 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.010

zbMATH Keywords

perfect Roman dominationperfect triple Roman dominationtrees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

The authors introduce perfect \([k]\)-Roman domination and focus on the case \(k=3\). For a labeling \(f:V(G)\to\{0,1,2,3,4\}\), the active neighborhood \(AN(v)\) consists of neighbors of \(v\) with nonzero labels. A perfect triple Roman dominating function satisfies, for every vertex \(v\) with \(f(v)<3\), \(\sum_{u\in N[v]} f(u)=|AN(v)|+3\). The corresponding invariant \(\gamma^{p}_{[3R]}(G)\) is the minimum weight \(\sum_{v\in V(G)} f(v)\).\N\NAlgorithmically, the decision problem for \(\gamma^{p}_{[3R]}(G)\) is shown to be NP-complete even for bipartite graphs. Exact values are determined for paths \(P_n\) and cycles \(C_n\), given by explicit (piecewise) formulas in terms of \(n\). For trees \(T\) of order \(n\ge 5\), the authors prove the sharp upper bound \(\gamma^{p}_{[3R]}(T)\le 2n-2\) and characterize the extremal trees attaining equality, namely healthy spiders, corona graphs of \(P_3\) and \(P_4\), and trees obtained from a corona of a tree by attaching one additional vertex to a support vertex. Several open problems are proposed.

Cites work

• A characterization of perfect Roman trees
• Algorithmic complexity of triple Roman dominating functions on graphs
• An improved upper bound on the double Roman domination number of graphs with minimum degree at least two
• An upper bound on triple Roman domination
• Double Roman domination
• Double Roman domination in graphs: algorithmic complexity
• Double Roman domination in trees
• Further results on the \([k]\)-Roman domination in graphs
• scientific article; zbMATH DE number 7693187 (Why is no real title available?)
• New results on quadruple Roman domination in graphs
• On [ k ] -Roman domination in graphs
• Perfect double Roman domination of trees
• Quadruple Roman domination in graphs
• Roman domination in graphs
• Signed double Roman domination in graphs
• Triple Roman domination in graphs
• Varieties of Roman Domination
• Varieties of Roman domination. II

This page was built for publication: Perfect triple Roman domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930353)