Some progress on the mixed roman domination in graphs

Ahangar, Hossein Abdollahzadeh; Amjadi, Jafar; Chellali, Mustapha; Kosari, Saeed; Samodivkin, Vladimir; Sheikholeslami, Seyed Mahmoud

doi:10.1051/ro/2020038

Ahangar, Hossein Abdollahzadeh ; Amjadi, Jafar ; Chellali, Mustapha ; Kosari, Saeed ; Samodivkin, Vladimir ; Sheikholeslami, Seyed Mahmoud

RAIRO. Operations Research, Tome 55 (2021), pp. S1411-S1423

Résumé

Let G = (V, E) be a simple graph with vertex set V and edge set E. A mixed Roman dominating function of G is a function f : V ∪ E → {0, 1, 2} satisfying the condition that every element x ∈ V ∪ E for which f(x) = 0 is adjacent or incident to at least one element y ∈ V ∪ E for which f(y) = 2. The weight of a mixed Roman dominating function f is ω(f) = ∑$$ f(x). The mixed Roman domination number $γ_{R}^{*} (G)$ of G is the minimum weight of a mixed Roman dominating function of G. We first show that the problem of computing $γ_{R}^{*} (G)$ is NP-complete for bipartite graphs and then we present upper and lower bounds on the mixed Roman domination number, some of them are for the class of trees.

MR Zbl

DOI : 10.1051/ro/2020038

Classification : 05C69
Keywords: Roman dominating function, Roman domination number, mixed Roman dominating function, mixed Roman domination number

@article{RO_2021__55_S1_S1411_0,
     author = {Ahangar, Hossein Abdollahzadeh and Amjadi, Jafar and Chellali, Mustapha and Kosari, Saeed and Samodivkin, Vladimir and Sheikholeslami, Seyed Mahmoud},
     title = {Some progress on the mixed roman domination in graphs},
     journal = {RAIRO. Operations Research},
     pages = {S1411--S1423},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020038},
     mrnumber = {4223085},
     zbl = {1469.05123},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020038/}
}

TY  - JOUR
AU  - Ahangar, Hossein Abdollahzadeh
AU  - Amjadi, Jafar
AU  - Chellali, Mustapha
AU  - Kosari, Saeed
AU  - Samodivkin, Vladimir
AU  - Sheikholeslami, Seyed Mahmoud
TI  - Some progress on the mixed roman domination in graphs
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S1411
EP  - S1423
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020038/
DO  - 10.1051/ro/2020038
LA  - en
ID  - RO_2021__55_S1_S1411_0
ER  -

%0 Journal Article
%A Ahangar, Hossein Abdollahzadeh
%A Amjadi, Jafar
%A Chellali, Mustapha
%A Kosari, Saeed
%A Samodivkin, Vladimir
%A Sheikholeslami, Seyed Mahmoud
%T Some progress on the mixed roman domination in graphs
%J RAIRO. Operations Research
%D 2021
%P S1411-S1423
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020038/
%R 10.1051/ro/2020038
%G en
%F RO_2021__55_S1_S1411_0

Ahangar, Hossein Abdollahzadeh; Amjadi, Jafar; Chellali, Mustapha; Kosari, Saeed; Samodivkin, Vladimir; Sheikholeslami, Seyed Mahmoud. Some progress on the mixed roman domination in graphs. RAIRO. Operations Research, Tome 55 (2021), pp. S1411-S1423. doi: 10.1051/ro/2020038

Bibliographie
Cité par

H. Abdollahzadeh Ahangar, M. Chellali and S. M. Sheikholeslami, Signed double Roman domination in graphs. Disc. Appl. Math. 257 (2019) 1–11. | MR | Zbl | DOI

H. Abdollahzadeh Ahangar, M. Chellali and S. M. Sheikholeslami, Outer independent double Roman domination. Appl. Math. Comput. 364 (2020) 124617. | MR | Zbl

H. Abdollahzadeh Ahangar, M. Chellali, S. M. Sheikholeslami and J. C. Valenzuela-Tripodoro, Total Roman {2}-domination in graphs. Discuss. Math. Graph Theory (to appear) DOI: (2020). | DOI | Zbl

H. Abdollahzadeh Ahangar, T. W. Haynes and J. C. Valenzuela-Tripodoro, Mixed Roman domination in graphs. Bull. Malays. Math. Sci. Soc. 40 (2017) 1443–1454. | MR | Zbl | DOI

M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad and M. S. Moradi, Properties of independent Roman domination in graphs. Australas. J. Comb. 52 (2012) 11–18. | MR | Zbl

Y. Alavi, M. Behzad, L. Lesniak and E. A. Nordhaus, Total matchings and total coverings of graphs. J. Graph Theory 1 (1977) 135–140. | MR | Zbl | DOI

Y. Alavi, J. Q. Liu, J. F. Wang and Z. F. Zhang, On total covers of graphs. Disc. Math. 100 (1992) 229–233. | MR | Zbl | DOI

J. Amjadi, Total Roman domination subdivision number in graphs. Commun. Comb. Optim. 5 (2020) 157–168. | MR | Zbl

D. Bange, A. E. Barkauskas and P. J. Slater, Efficient dominating sets in graphs, edited by R. D. Ringeisen and F. S. Roberts. In: Applications of Discrete Math. SIAM, Philadelphia, PA (1988) 189–199. | MR | Zbl

S. Bermudo, H. Fernau and J. M. Sigarreta, The differential and the Roman domination number of a graph. Appl. Anal. Disc. Math. 8 (2014) 155–171. | MR | Zbl | DOI

M. Chellali and N. Jafari Rad, A note on the independent Roman domination in unicyclic graphs. Opuscula Math. 32 (2012) 715–718. | MR | Zbl | DOI

M. Chellali and N. Jafari Rad, Strong equality between the Roman domination and independent Roman domination numbers in trees. Discuss. Math. Graph Theory 33 (2013) 337–346. | MR | Zbl | DOI

E. J. Cockayne, P. M. Dreyer, Sr., S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs. Disc. Math. 278 (2004) 11–22. | MR | Zbl | DOI

E. Ebrahimi Targhi, N. Jafari Rad, C. M. Mynhardt and Y. Wu, Bounds for the independent Roman domination number in graphs. J. Comb. Math. Comb. Comput. 80 (2012) 351–365. | MR | Zbl

P. Erdös and A. Meir, On total matching numbers and total covering numbers of complementary graphs. Disc. Math. 19 (1977) 229–233. | MR | Zbl | DOI

G. Hao, L. Volkmann and D. A. Mojdeh, Total double Roman domination in graphs. Commun. Comb. Optim. 5 (2020) 27–39. | MR | Zbl

G. Gunther, B. Hartnell, L. R. Markus and D. Rall, Graphs with unique minimum dominating sets. Congr. Numer. 101 (1994) 55–63. | MR | Zbl

P. Hatami, An approximation algorithm for the total covering problem. Discuss. Math. Graph Theory 27 (2007) 553–558. | MR | Zbl | DOI

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York, NY (1998). | MR | Zbl

S. T. Hedetniemi, R. R. Rubalcaba, P. J. Slater and M. Walsh, Few compare to the great Roman empire. Congr. Numer. 217 (2013) 129–136. | MR | Zbl

J. K. Lan and G. J. Chang, On the mixed domination problem in graphs. Theor. Comput. Sci. 476 (2013) 84–93. | MR | Zbl | DOI

C. S. Revelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107 (2000) 585–594. | MR | Zbl | DOI

E. Sampathkumar and S. S. Kamath, Mixed domination in graphs. Sankayā: Indian J. Stat. 54 (1992) 399–402. | MR | Zbl

I. Stewart, Defend the Roman empire! Sci. Am. 281 (1999) 136–139. | DOI

L. Volkmann, Weak signed Roman domination in graphs. Commun. Comb. Optim. 5 (2020) 111–123. | MR | Zbl

Cité par Sources :