Publications
Sort:
Open Access Research Article Issue
Vertex-edge perfect Roman domination number
AIMS Mathematics 2023, 8(9): 21472-21483
Published: 15 September 2023
Abstract PDF (266.6 KB) Collect
Downloads:0

A vertex-edge perfect Roman dominating function on a graph G = ( V , E ) (denoted by ve-PRDF) is a function f : V ( G ) { 0 , 1 , 2 } such that for every edge u v E, max { f ( u ) , f ( v ) } 0, 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 ) = v V f ( v ). The vertex-edge perfect Roman domination number of G (denoted by γ v e R 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 γ v e R p ( T ) in terms of the order n, l leaves and s support vertices. Lastly, we determine γ v e R p ( G ) for Petersen, cycle and Flower snark graphs.

Total 1