Vertex-edge perfect Roman domination number

Bana Al Subaiei; Ahlam AlMulhim; Abolape Deborah Akwu; Bana Al Subaiei; Ahlam AlMulhim; Abolape Deborah Akwu

doi:10.3934/math.20231094

AIMS Mathematics

2023, Volume 8, Issue 9: 21472-21483. doi: 10.3934/math.20231094

Previous Article Next Article

Research article

Vertex-edge perfect Roman domination number

1.
Department of Mathematics and Statistics, College of Science, King Faisal University, P. O. Box 400, Al-Ahsa, 31982, Saudi Arabia
2.
Department of Mathematics, College of Science, Federal University of Agriculture, Makurdi, Nigeria

Received: 07 April 2023 Revised: 17 June 2023 Accepted: 25 June 2023 Published: 05 July 2023
MSC : 05C05, 05C69

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.
- vertex-edge perfect domination number,
- trees,
- cycles,
- Petersen graph,
- bipartite graph
Citation: Bana Al Subaiei, Ahlam AlMulhim, Abolape Deborah Akwu. Vertex-edge perfect Roman domination number[J]. AIMS Mathematics, 2023, 8(9): 21472-21483. doi: 10.3934/math.20231094

Related Papers:

Abstract

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.

References

[1]	A. Almulhim, A. Akwu, B. Al Subaiei, The perfect roman domination number of the cartesian product of some graphs, J. Math., 2022 (2022), 1957027. http://dx.doi.org/10.1155/2022/1957027 doi: 10.1155/2022/1957027
[2]	G. Chang, S. Chen, C. Liu, Edge Roman domination on graphs, Graph. Combinator., 32 (2016), 1731–1747. http://dx.doi.org/10.1007/s00373-016-1695-x doi: 10.1007/s00373-016-1695-x
[3]	E. Cockayne, P. Dreyer, S. Hedetniemi, S. Hedetniemi, Roman domination in graphs, Discrete Math., 278 (2004), 11–22. http://dx.doi.org/10.1016/j.disc.2003.06.004
[4]	I. Dejter, Perfect domination in regular grid graphs, Australas. J. Comb., 42 (2008), 99–114.
[5]	T. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs, Boca Raton: CRC Press, 1998. http://dx.doi.org/10.1201/9781482246582
[6]	M. Henning, W. Klostermeyer, G. MacGillivray, Perfect Roman domination in trees, Discrete Appl. Math., 236 (2018), 235–245. http://dx.doi.org/10.1016/j.dam.2017.10.027 doi: 10.1016/j.dam.2017.10.027
[7]	S. Jena, G. Das, Vertex-edge domination in unit disk graphs, Discrete Appl. Math., 319 (2022), 351–361, http://dx.doi.org/10.1016/j.dam.2021.06.002 doi: 10.1016/j.dam.2021.06.002
[8]	S. Mitchell, S. Hedetniemi, Edge domination in trees, Proceedings of 8th SE Conference Combinatorics, Graph, Theory and Computing, 19 (1977), 489–509.
[9]	H. Naresh Kumar, Y. Venkatakrishnan, Trees with vertex-edge Roman domination number twice the domination number minus one, Proyecciones, 39 (2020), 1381–1392, http://dx.doi.org/10.22199/issn.0717-6279-2020-06-0084 doi: 10.22199/issn.0717-6279-2020-06-0084
[10]	H. Naresh Kumar, Y. Venkatakrishnan, Vertex-edge Roman domination, Kragujev. J. Math., 45 (2021), 685–698.
[11]	K. Peters, Theoretical and algorithmic results on domination and connectivity, Ph. D Thesis, Clemson University, 1986.
[12]	S. Vaidya, R. Pandit, Edge domination in some path and cycle relate graphs, J. Math., 2014 (2014), 975812. http://dx.doi.org/10.1155/2014/975812 doi: 10.1155/2014/975812
[13]	P. Zyliński, Vertex-edge domination in graphs, Aequat. Math., 93 (2019), 735–742. http://dx.doi.org/10.1007/s00010-018-0609-9 doi: 10.1007/s00010-018-0609-9

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)