On the double Roman domination in graphs Abdollahzadeh Ahangar, Hossein; Chellali, Mustapha; Sheikholeslami, Seyed Mahmoud
Discrete Applied Mathematics,
12/2017, Volume:
232
Journal Article
Peer reviewed
Open access
A double Roman dominating function (DRDF) on a graph G=(V,E) is a function f:V(G)→{0,1,2,3} having the property that if f(v)=0, then vertex v has at least two neighbors assigned 2 under f or one ...neighbor w with f(w)=3, and if f(v)=1, then vertex v must have at least one neighbor w with f(w)≥2. The weight of a DRDF is the value f(V(G))=∑u∈V(G)f(u). The double Roman domination number γdR(G) is the minimum weight of a DRDF on G. First we show that the decision problem associated with γdR(G) is NP-complete for bipartite and chordal graphs. Then we present some sharp bounds on the double Roman domination number which partially answer an open question posed by Beeler et al. (2016) in their introductory paper on double Roman domination. Moreover, a characterization of graphs G with small γdR(G) is provided.
For an integer
k
≥ 1, a Roman {
k
}-dominating function (R{
k
}DF) on a graph
G
= (
V
,
E
) is a function
f
:
V
→ {0, 1, …,
k
} such that for every vertex
v
∈
V
with
f
(
v
) = 0, ∑
u
∈
N
(
v
...)
f
(
u
) ≥
k
, where
N
(
v
) is the set of vertices adjacent to
v
. The weight of an R{
k
}DF is the sum of its function values over the whole set of vertices, and the Roman {
k
}-domination number
γ
{
kR
}
(
G
) is the minimum weight of an R{
k
}DF on
G
. In this paper, we will be focusing on the case
k
= 3, where trivially for every connected graphs of order
n
≥ 3, 3 ≤
γ
{
kR
}
(
G
) ≤
n
. We characterize all connected graphs
G
of order
n
≥ 3 such that
γ
{3
R
}
(
G
) ∈ {3,
n
− 1,
n
}, and we improve the previous lower and upper bounds. Moreover, we show that for every tree
T
of order
n
≥ 3,
γ
{3
R
}
(
T
) ≥
γ
(
T
) + 2, where
γ
(
T
) is the domination number of
T
, and we characterize the trees attaining this bound.
Outer independent Roman dominating functions in graphs Abdollahzadeh Ahangar, Hossein; Chellali, Mustapha; Samodivkin, Vladimir
International journal of computer mathematics,
12/2017, Volume:
94, Issue:
12
Journal Article
Peer reviewed
A Roman dominating function (RDF) on a graph G is a function
satisfying the condition that every vertex u for which
is adjacent to at least one vertex v for which
. A function
is an outer-independent ...Roman dominating function (OIRDF) on G if f is an RDF and
is an independent set. The outer-independent Roman domination number
is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number
is NP-complete for bipartite graphs. Then we present lower and upper bounds on
. Moreover, we characterize graphs with small or large outer-independent Roman domination number.
A 2-rainbow dominating function (2RDF) of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all subsets of the set $\{1,2\}$ such that for any vertex $v\in V(G)$ with ...$f(v)=\emptyset$ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$ is fulfilled, where $N(v)$ is the open neighborhood of $v$. A maximal 2-rainbow dominating function of a graph $G$ is a $2$-rainbow dominating function $f$ such that the set $\{w\inV(G)|f(w)=\emptyset\}$ is not a dominating set of $G$. The weight of a maximal 2RDF $f$ is the value $\omega(f)=\sum_{v\in V}|f (v)|$. The maximal $2$-rainbow domination number of a graph $G$, denoted by $\gamma_{m2r}(G)$, is the minimum weight of a maximal 2RDF of $G$. In this paper, we continue the study of maximal 2-rainbow domination {number} in graphs. Specially, we first characterize all graphs with large maximal 2-rainbow domination number. Finally, we determine the maximal $2$-rainbow domination number in the sun and sunlet graphs.
On maximal Roman domination in graphs Abdollahzadeh Ahangar, Hossein; Chellali, Mustapha; Kuziak, Dorota ...
International journal of computer mathematics,
07/2016, Volume:
93, Issue:
7
Journal Article
Peer reviewed
A Roman dominating function (RDF) for a graph
is a function
satisfying the condition that every vertex u of G for which
is adjacent to at least one vertex v of G for which
. The weight of a RDF f is ...the sum
, and the minimum weight of a RDF for G is the Roman domination number,
of G. A maximal RDF for a graph G is a RDF f such that
is not a dominating set of G. The maximal Roman domination number,
of a graph G equals the minimum weight of a maximal RDF for G. We first show that determining the number
for an arbitrary graph G is NP-complete even when restricted to bipartite or planar graphs. Then, we characterize connected graphs G such that
. We also provide a characterization of all trees T of order n such that
.
Graphs with Large Geodetic Number Ahangar, Hossein Abdollahzadeh; Kosari, Saeed; Sheikholeslami, Seyed Mahmoud ...
Filomat,
01/2015, Volume:
29, Issue:
6
Journal Article
Peer reviewed
Open access
For two vertices 𝑢 and 𝑣 of a graph 𝐺, the set 𝐼𝑢, 𝑣 consists of all vertices lying on some 𝑢 - 𝑣 geodesic in 𝐺. If 𝑆 is a set of vertices of 𝐺, then 𝐼𝑆 is the union of all sets 𝐼𝑢, 𝑣 ...for 𝑢, 𝑣 ϵ 𝑆. A subset 𝑆 of vertices of 𝐺 is ageodetic setif 𝐼𝑆 = 𝑣. Thegeodetic number𝑔(𝐺) is the minimum cardinality of a geodetic set of 𝐺. It was shown that a connected graph 𝐺 of order 𝑛 ≥ 3 has geodetic number 𝑛 − 1 if and only if 𝐺 is the join of 𝐾₁ and pairwise disjoint complete graphs
K
n
1
,
K
n
2
,
…
,
K
n
r
, that is,
G
=
(
K
n
1
∪
K
n
2
∪
…
K
n
r
)
+
K
1
, where 𝑟 ≥ 2, 𝑛₁, 𝑛₂,..., 𝑛𝑟are positive integers with 𝑛₁ + 𝑛₂ + ... + 𝑛𝑟= 𝑛 − 1. In this paper we characterize all connected graphs 𝐺 of order 𝑛 ≥ 3 with 𝑔(𝐺) = 𝑛 − 2.
PDF
