Back to Search
Start Over
Isolate Roman domination in graphs.
- Source :
- Discrete Mathematics, Algorithms & Applications; May2022, Vol. 14 Issue 3, p1-12, 12p
- Publication Year :
- 2022
-
Abstract
- Let G be a graph with the vertex set V. A function f : V → { 0 , 1 , 2 } is called a Roman dominating function of G , if every vertex v with f (v) = 0 is adjacent to at least one vertex u with f (u) = 2. The weight of a Roman dominating function f is equal to ∑ v ∈ V (G) f (v). The minimum weight of a Roman dominating function of G is called the Roman domination number of G , denoted by γ R (G). In this paper, we initiate the study of a variant of Roman dominating functions. A function f : V (G) → { 0 , 1 , 2 } is called an isolate Roman dominating function of G , if f is a Roman dominating function and there is a vertex v with f (v) = 0 which is not adjacent to any vertex u with f (u) = 0. The minimum weight of an isolate Roman dominating function of G is called the isolate Roman domination number of G , denoted by γ I R (G). We present some upper bound on the isolate Roman domination number of a graph G in terms of its Roman domination number and its domination number. Moreover, we present some classes of graphs G with γ I R (G) = γ R (G). Finally, we show that the decision problem associated with the isolate Roman dominating functions is NP-complete for bipartite graphs and chordal graphs. [ABSTRACT FROM AUTHOR]
- Subjects :
- DOMINATING set
BIPARTITE graphs
STATISTICAL decision making
ROMANS
Subjects
Details
- Language :
- English
- ISSN :
- 17938309
- Volume :
- 14
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics, Algorithms & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 156279498
- Full Text :
- https://doi.org/10.1142/S1793830921501317