A Note on Roman Domination of Digraphs

Discussiones Mathematicae Graph Theory

Chen Xiaodan¹  Hao Guoliang²  Xie Zhihong² 

[1] College of Mathematics and Information Science Guangxi UniversityNanning, P.R. China;College of Science East China University of TechnologyNanchang, P.R. China;

关键词: roman domination number;    domination number;    digraph;    nordhaus-gaddum;    05c69;    05c20;   

DOI  :  10.7151/dmgt.2067

来源: DOAJ

【 摘 要 】

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of a digraph D, denoted by γ(D), is the minimum cardinality of a dominating set of D. A Roman dominating function (RDF) on a digraph D is a function f : V (D) → {0, 1, 2} satisfying the condition that every vertex v with f(v) = 0 has an in-neighbor u with f(u) = 2. The weight of an RDF f is the value ω (f) =Σv∈V(D)f(v). The Roman domination number of a digraph D, denoted by γR(D), is the minimum weight of an RDF on D. In this paper, for any integer k with 2 ≤ k ≤ γ(D), we characterize the digraphs D of order n ≥ 4 with δ−(D) ≥ 1 for which γR(D) = (D) + k holds. We also characterize the digraphs D of order n ≥ k with γR(D) = k for any positive integer k. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.

【 授权许可】

Unknown