Roman domination in direct product graphs and rooted product graphs
Let $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is th...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2021-08-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.2021643?viewType=HTML |
| _version_ | 1824009200877961216 |
|---|---|
| author | Abel Cabrera Martínez Iztok Peterin Ismael G. Yero |
| author_facet | Abel Cabrera Martínez Iztok Peterin Ismael G. Yero |
| author_sort | Abel Cabrera Martínez |
| collection | DOAJ |
| description | Let $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all Roman dominating functions $ f $ on $ G $. In this article we study the Roman domination number of direct product graphs and rooted product graphs. Specifically, we give several tight lower and upper bounds for the Roman domination number of direct product graphs involving some parameters of the factors, which include the domination, (total) Roman domination, and packing numbers among others. On the other hand, we prove that the Roman domination number of rooted product graphs can attain only three possible values, which depend on the order, the domination number, and the Roman domination number of the factors in the product. In addition, theoretical characterizations of the classes of rooted product graphs achieving each of these three possible values are given. |
| first_indexed | 2024-12-18T21:07:20Z |
| format | Article |
| id | doaj.art-57419cd95dd74d7f84f4eabe98d4a234 |
| institution | Directory Open Access Journal |
| issn | 2473-6988 |
| language | English |
| last_indexed | 2024-12-18T21:07:20Z |
| publishDate | 2021-08-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | AIMS Mathematics |
| spelling | doaj.art-57419cd95dd74d7f84f4eabe98d4a2342022-12-21T20:52:38ZengAIMS PressAIMS Mathematics2473-69882021-08-01610110841109610.3934/math.2021643Roman domination in direct product graphs and rooted product graphsAbel Cabrera Martínez0Iztok Peterin 1Ismael G. Yero21. Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Spain2. University of Maribor, Faculty of Electrical Engineering and Computer Science, Slovenia 3. IMFM, Jadranska 19, 1000 Ljubljana, Slovenia4. Universidad de Cádiz, Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras, SpainLet $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all Roman dominating functions $ f $ on $ G $. In this article we study the Roman domination number of direct product graphs and rooted product graphs. Specifically, we give several tight lower and upper bounds for the Roman domination number of direct product graphs involving some parameters of the factors, which include the domination, (total) Roman domination, and packing numbers among others. On the other hand, we prove that the Roman domination number of rooted product graphs can attain only three possible values, which depend on the order, the domination number, and the Roman domination number of the factors in the product. In addition, theoretical characterizations of the classes of rooted product graphs achieving each of these three possible values are given.https://www.aimspress.com/article/doi/10.3934/math.2021643?viewType=HTMLroman dominationdominationdirect product graphrooted product graph |
| spellingShingle | Abel Cabrera Martínez Iztok Peterin Ismael G. Yero Roman domination in direct product graphs and rooted product graphs AIMS Mathematics roman domination domination direct product graph rooted product graph |
| title | Roman domination in direct product graphs and rooted product graphs |
| title_full | Roman domination in direct product graphs and rooted product graphs |
| title_fullStr | Roman domination in direct product graphs and rooted product graphs |
| title_full_unstemmed | Roman domination in direct product graphs and rooted product graphs |
| title_short | Roman domination in direct product graphs and rooted product graphs |
| title_sort | roman domination in direct product graphs and rooted product graphs |
| topic | roman domination domination direct product graph rooted product graph |
| url | https://www.aimspress.com/article/doi/10.3934/math.2021643?viewType=HTML |
| work_keys_str_mv | AT abelcabreramartinez romandominationindirectproductgraphsandrootedproductgraphs AT iztokpeterin romandominationindirectproductgraphsandrootedproductgraphs AT ismaelgyero romandominationindirectproductgraphsandrootedproductgraphs |