Vertex-edge perfect Roman domination number
A vertex-edge perfect Roman dominating function on a graph $ G = (V, E) $ (denoted by ve-PRDF) is a function $ f:V\left(G\right)\longrightarrow\{0, 1, 2\} $ such that for every edge $ uv\in E $, $ \max\{f(u), f(v)\}\neq0 $, or $ u $ is adjacent to exactly one neighbor $ w $ such that $ f(w) = 2 $, o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2023-07-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.20231094?viewType=HTML |
| _version_ | 1797778034578685952 |
|---|---|
| author | Bana Al Subaiei Ahlam AlMulhim Abolape Deborah Akwu |
| author_facet | Bana Al Subaiei Ahlam AlMulhim Abolape Deborah Akwu |
| author_sort | Bana Al Subaiei |
| collection | DOAJ |
| description | A vertex-edge perfect Roman dominating function on a graph $ G = (V, E) $ (denoted by ve-PRDF) is a function $ f:V\left(G\right)\longrightarrow\{0, 1, 2\} $ such that for every edge $ uv\in E $, $ \max\{f(u), f(v)\}\neq0 $, or $ u $ is adjacent to exactly one neighbor $ w $ such that $ f(w) = 2 $, or $ v $ is adjacent to exactly one neighbor $ w $ such that $ f(w) = 2 $. The weight of a ve-PRDF on $ G $ is the sum $ w(f) = \sum_{v\in V}f(v) $. The vertex-edge perfect Roman domination number of $ G $ (denoted by $ \gamma_{veR}^{p}(G) $) is the minimum weight of a ve-PRDF on $ G $. In this paper, we first show that vertex-edge perfect Roman dominating is NP-complete for bipartite graphs. Also, for a tree $ T $, we give upper and lower bounds for $ \gamma_{veR}^{p}(T) $ in terms of the order $ n $, $ l $ leaves and $ s $ support vertices. Lastly, we determine $ \gamma_{veR}^{p}(G) $ for Petersen, cycle and Flower snark graphs. |
| first_indexed | 2024-03-12T23:11:30Z |
| format | Article |
| id | doaj.art-5e5c2418926147f0892e51c74f39b888 |
| institution | Directory Open Access Journal |
| issn | 2473-6988 |
| language | English |
| last_indexed | 2024-03-12T23:11:30Z |
| publishDate | 2023-07-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | AIMS Mathematics |
| spelling | doaj.art-5e5c2418926147f0892e51c74f39b8882023-07-18T01:32:20ZengAIMS PressAIMS Mathematics2473-69882023-07-0189214722148310.3934/math.20231094Vertex-edge perfect Roman domination numberBana Al Subaiei0Ahlam AlMulhim1Abolape Deborah Akwu 21. Department of Mathematics and Statistics, College of Science, King Faisal University, P. O. Box 400, Al-Ahsa, 31982, Saudi Arabia1. Department of Mathematics and Statistics, College of Science, King Faisal University, P. O. Box 400, Al-Ahsa, 31982, Saudi Arabia2. Department of Mathematics, College of Science, Federal University of Agriculture, Makurdi, NigeriaA vertex-edge perfect Roman dominating function on a graph $ G = (V, E) $ (denoted by ve-PRDF) is a function $ f:V\left(G\right)\longrightarrow\{0, 1, 2\} $ such that for every edge $ uv\in E $, $ \max\{f(u), f(v)\}\neq0 $, or $ u $ is adjacent to exactly one neighbor $ w $ such that $ f(w) = 2 $, or $ v $ is adjacent to exactly one neighbor $ w $ such that $ f(w) = 2 $. The weight of a ve-PRDF on $ G $ is the sum $ w(f) = \sum_{v\in V}f(v) $. The vertex-edge perfect Roman domination number of $ G $ (denoted by $ \gamma_{veR}^{p}(G) $) is the minimum weight of a ve-PRDF on $ G $. In this paper, we first show that vertex-edge perfect Roman dominating is NP-complete for bipartite graphs. Also, for a tree $ T $, we give upper and lower bounds for $ \gamma_{veR}^{p}(T) $ in terms of the order $ n $, $ l $ leaves and $ s $ support vertices. Lastly, we determine $ \gamma_{veR}^{p}(G) $ for Petersen, cycle and Flower snark graphs.https://www.aimspress.com/article/doi/10.3934/math.20231094?viewType=HTMLvertex-edge perfect domination numbertreescyclespetersen graphbipartite graph |
| spellingShingle | Bana Al Subaiei Ahlam AlMulhim Abolape Deborah Akwu Vertex-edge perfect Roman domination number AIMS Mathematics vertex-edge perfect domination number trees cycles petersen graph bipartite graph |
| title | Vertex-edge perfect Roman domination number |
| title_full | Vertex-edge perfect Roman domination number |
| title_fullStr | Vertex-edge perfect Roman domination number |
| title_full_unstemmed | Vertex-edge perfect Roman domination number |
| title_short | Vertex-edge perfect Roman domination number |
| title_sort | vertex edge perfect roman domination number |
| topic | vertex-edge perfect domination number trees cycles petersen graph bipartite graph |
| url | https://www.aimspress.com/article/doi/10.3934/math.20231094?viewType=HTML |
| work_keys_str_mv | AT banaalsubaiei vertexedgeperfectromandominationnumber AT ahlamalmulhim vertexedgeperfectromandominationnumber AT abolapedeborahakwu vertexedgeperfectromandominationnumber |