Article in volume
Authors:
Mustapha Chellali
Department of MathematicsUniversity of BlidaB.P. 270, Blida, ALGERIA
email: m_chellali@yahoo.com
Seyed Mahmoud Sheikholeslami
Azarbaijan Shahid Madani university
Title:
Total Roman $\{2\}$-dominating functions in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 937-958
Received: 2019-10-29 , Revised: 2020-03-02 , Accepted: 2020-03-23 , Available online: 2020-04-18 , https://doi.org/10.7151/dmgt.2316
Abstract:
A Roman $\{2\}$-dominating function (R2F) is a function $f:V\rightarrow
\{0,1,2\}$ with the property that for every vertex $v\in V$ with $f(v)=0$
there is a neighbor $u$ of $v$ with $f(u)=2$, or there are two neighbors $x,y$
of $v$ with $f(x)=f(y)=1$. A total Roman $\{2\}$-dominating function (TR2DF)
is an R2F $f$ such that the set of vertices with $f(v)>0$ induce a subgraph
with no isolated vertices. The weight of a TR2DF is the sum of its function
values over all vertices, and the minimum weight of a TR2DF of $G$ is the
total Roman $\{2\}$-domination number $\gamma_{tR2}(G).$ In this paper, we
initiate the study of total Roman $\{2\}$-dominating functions, where properties
are established. Moreover, we present various bounds on the total Roman
$\{2\}$-domination number. We also show that the decision problem associated
with $\gamma_{tR2}(G)$ is NP-complete for bipartite and chordal graphs.
Moreover, we show that it is possible to compute this parameter in linear time
for bounded clique-width graphs (including trees).
Keywords:
Roman domination, Roman $\{2\}$-domination, total Roman $\{2\}$-domination
References:
- B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249.
https://doi.org/10.1002/jgt.3190030306 - M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28.
https://doi.org/10.1016/j.dam.2015.11.013 - H. Chen and C. Lu, A note on Roman ${2}$-domination problem in graphs (804-09338).
- E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22.
https://doi.org/10.1016/j.disc.2003.06.004 - B. Courcelle, J.A. Makowsky and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2000) 125–150.
https://doi.org/10.1007/s002249910009 - F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.
- W. Klostermeyer and G. MacGillivray, Roman, Italian, and $2$-domination, J. Combin. Math. Combin. Comput. 108 (2019) 125–146.
- M. Liedloff, T. Kloks, J. Liu and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008) 3400–3415.
https://doi.org/10.1016/j.dam.2008.01.011 - C.S. ReVelle, Can you protect the Roman Empire?, Johns Hopkins Magazine 49 (1997) 40.
- C.S. ReVelle and K.E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594.
https://doi.org/10.1080/00029890.2000.12005243 - I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136–139.
https://doi.org/10.1038/scientificamerican1299-136
Close