Article in volume
Authors:
Seyed Mahmoud Sheikholeslami
Azarbaijan Shahid Madani university
Title:
Some results on the global triple Roman domination in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 725-754
Received: 2024-01-04 , Revised: 2024-06-14 , Accepted: 2024-06-15 , Available online: 2024-09-07 , https://doi.org/10.7151/dmgt.2558
Abstract:
A triple Roman dominating function (TRDF) on a graph $G$ with vertex set $V$ is
a function $f:V\rightarrow\{0,1,2,3,4\}$ such that for any vertex $v\in V$ with
$f(v)<3,$ $\sum_{x\in N(v)\cup\{v\}}f(x)\ge|\{x\in N(v):f(x)\ge1\}|+3$, where
$N(v)$ is the open neighborhood of $v.$ The weight of a TRDF $f$ is the value
$\sum_{v\in V}f(v).$ A global triple Roman dominating function (GTRDF) on $G$
is a TRDF on both $G$ and its complement. The minimum weight of a GTRDF on $G$
is called the global triple Roman domination number $\gamma_{g[3R]}(G)$ of $G.$
We first show that for any tree $T$ on $n\ge5$ vertices, $\gamma_{g[3R]}(T)
\le7n/4$ and characterize all extremal trees. We also show that for any graph
$G$ on $n$ vertices, $\gamma_{g[3R]}(G)\ne3n-3,$ and further characterize all
graphs $G$ with $\gamma_{g[3R]}(G)=3n-k$ for each $k\in\{4,5,6,7\},$ which
improves the results given by Nahani Pour et al. (2022).
Keywords:
global triple Roman domination, triple Roman domination, complement, characterization
References:
- H. Abdollahzadeh Ahangar, M.P. Álvarez, M. Chellali, S.M. Sheikholeslami and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Appl. Math. Comput. 391 (2021) 125444.
https://doi.org/10.1016/j.amc.2020.125444 - H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A Sci. 43 (2019) 1081–1088.
https://doi.org/10.1007/s40995-018-0535-7 - R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29.
https://doi.org/10.1016/j.dam.2016.03.017 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T.Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 64, (Springer, Cham, 2020) 365–409.
https://doi.org/10.1007/978-3-030-51117-3_11 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 66, (Springer, Cham, 2021) 273–307.
https://doi.org//10.1007/978-3-030-58892-2_10 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020) 966–984.
https://doi.org/10.1016/j.akcej.2019.12.001 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: a survey, Discuss. Math. Graph Theory 42 (2022) 861–891.
https://doi.org/10.7151/dmgt.2313 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141–171.
- A.T. Egunjobi and T.W. Haynes, Perfect double Roman domination of trees, Discrete Appl. Math. 284 (2020) 71–85.
https://doi.org/10.1016/j.dam.2020.03.021 - M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao and S.M. Sheikholeslami, New bounds on the triple Roman domination number of graphs, J. Math. 2022 (2022) 9992618.
https://doi.org/10.1155/2022/9992618 - G. Hao, L. Volkmann and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020) 27–39.
https://doi.org/10.22049/cco.2019.26484.1118 - N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53.
https://doi.org/10.7151/dmgt.2069 - R. Khoeilar, M. Chellali, H. Karami and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019) 159–167.
https://doi.org/10.1016/j.dam.2019.06.018 - F. Nahani Pour, H. Abdollahzadeh Ahangar, M. Chellali and S.M. Sheikholeslami, Global triple Roman dominating function, Discrete Appl. Math. 314 (2022) 228–237.
https://doi.org/10.1016/j.dam.2022.02.015 - A. Poureidi, Double Roman domination in graphs: algorithmic complexity, Commun. Comb. Optim. 8 (2023) 491–503.
https://doi.org/10.22049/cco.2022.27661.1309 - A. Poureidi and J. Fathali, Algorithmic complexity of triple Roman dominating functions on graphs, Commun. Comb. Optim. 9 (2024) 217–232.
https://doi.org/10.22049/cco.2023.27884.1385 - L. Ouldrabah and L. Volkmann, An upper bound on the double Roman domination number, Bull. Iranian Math. Soc. 47 (2021) 1315–1323.
https://doi.org/10.1007/s41980-020-00442-1 - Z. Shao, R. Khoeilar, H. Karami, M. Chellali and S.M. Sheikholeslami, Disprove of a conjecture on the double Roman domination number, Aequationes Math. 98 (2024) 241–260.
https://doi.org/10.1007/s00010-023-01029-x - L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018) 71–77.
https://doi.org/10.22049/cco.2018.26125.1078
Close