Loading…
Co-Roman domination in graphs
Let G = ( V , E ) be a graph and let f : V → {0, 1, 2} be a function. A vertex u is said to be protected with respect to f if f ( u ) > 0 or f ( u ) = 0 and u is adjacent to a vertex with positive weight. The function f is a co-Roman dominating function (CRDF) if: (i) every vertex in V is protect...
Saved in:
| Published in: | Proceedings of the Indian Academy of Sciences. Mathematical sciences 2015-02, Vol.125 (1), p.1-10 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Let
G
= (
V
,
E
) be a graph and let
f
:
V
→ {0, 1, 2} be a function. A vertex
u
is said to be protected with respect to
f
if
f
(
u
) > 0 or
f
(
u
) = 0 and
u
is adjacent to a vertex with positive weight. The function
f
is a co-Roman dominating function (CRDF) if: (i) every vertex in
V
is protected, and (ii) each
v
∈
V
with
f
(
v
) > 0 has a neighbor
u
∈
V
with
f
(
u
) = 0 such that the function
f
vu
:
V
→ {0, 1, 2}, defined by
f
vu
(
u
) = 1,
f
vu
(
v
) =
f
(
v
) −1 and
f
vu
(
x
) =
f
(
x
) for
x
∈
V
∖ {
u
,
v
} has no unprotected vertex. The weight of
f
is
w
(
f
)
=
∑
v
∈
V
f
(
v
)
. The co-Roman domination number of a graph
G
, denoted by
γ
c
r
(
G
), is the minimum weight of a co-Roman dominating function on
G
. In this paper we initiate a study of this parameter, present several basic results, as well as some applications and directions for further research. We also show that the decision problem for the co-Roman domination number is NP-complete, even when restricted to bipartite, chordal and planar graphs. |
|---|---|
| ISSN: | 0253-4142 0973-7685 |
| DOI: | 10.1007/s12044-015-0209-8 |