Extremal Graphs for a Bound on the Roman Domination Number
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 771-785
Voir la notice de l'article provenant de la source Library of Science
A Roman dominating function on a graph G = (V, E) is a function f:V (G) → 0, 1, 2 such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value w(f) = Σu∈V(G) f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G) ≤ n + 1 − Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G) = n + 1 − Δ is co-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for γR(G) + γR (Ḡ), where Ḡ is the complement graph of G.
Keywords:
Roman domination, Roman domination number, Nordhaus-Gaddum inequalities
@article{DMGT_2020_40_3_a4,
author = {Bouchou, Ahmed and Blidia, Mostafa and Chellali, Mustapha},
title = {Extremal {Graphs} for a {Bound} on the {Roman} {Domination} {Number}},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {771--785},
publisher = {mathdoc},
volume = {40},
number = {3},
year = {2020},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a4/}
}
TY - JOUR AU - Bouchou, Ahmed AU - Blidia, Mostafa AU - Chellali, Mustapha TI - Extremal Graphs for a Bound on the Roman Domination Number JO - Discussiones Mathematicae. Graph Theory PY - 2020 SP - 771 EP - 785 VL - 40 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a4/ LA - en ID - DMGT_2020_40_3_a4 ER -
%0 Journal Article %A Bouchou, Ahmed %A Blidia, Mostafa %A Chellali, Mustapha %T Extremal Graphs for a Bound on the Roman Domination Number %J Discussiones Mathematicae. Graph Theory %D 2020 %P 771-785 %V 40 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a4/ %G en %F DMGT_2020_40_3_a4
Bouchou, Ahmed; Blidia, Mostafa; Chellali, Mustapha. Extremal Graphs for a Bound on the Roman Domination Number. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 771-785. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a4/