Computing Roman domatic number of graphs

Tan, Haisheng1; Liang, Hongyu2; Wang, Rui3; Zhou, Jipeng1

2016-09

10.1016/j.ip1.2016.04.010

INFORMATION PROCESSING LETTERS   影响因子和分区

0020-0190

1872-6119

A Roman dominating function on a graph G = (V, E) is a mapping: V -> {0, 1, 2} satisfying that every vertex v is an element of V with f(v) = 0 is adjacent to some vertex u is an element of V with f(u) = 2. A Roman dominating family (of functions) on G is a set {f(1), f(2), ..., f(d)} of Roman dominating functions on G with the property that Sigma(d)(i=1) f(i)(v) <= 2 for all v is an element of V. The Roman domatic number of G, introduced by Sheikholeslami and Volkmann in 2010 [1], is the maximum number of functions in a Roman dominating family on G. In this paper, we study the Roman domatic number from both algorithmic complexity and graph theory points of view. We show that it is NP-complete to decide whether the Roman domatic number is at least 3, even if the graph is bipartite. To the best of our knowledge, this is the first computational hardness result concerning this concept. We also present an asymptotically optimal approximation threshold of Theta(logn) for computing the Roman domatic number of a graph. Moreover, we determine the Roman domatic number of some particular classes of graphs, such as fans, wheels and complete bipartite graphs. (C) 2016 Elsevier B.V. All rights reserved.

Roman domatic number Graph Computational complexity Approximation algorithms

SCI ; EI

英语

通讯

Sci., Tech. and Innovation Commission of Shenzhen Municipality Grant[KQCX2014052215132295]

Computer Science

Computer Science, Information Systems

WOS:000377736400003

ELSEVIER SCIENCE BV

20161902368470

Approximation algorithms ; Computational complexity ; Parallel processing systems

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Digital Computers and Systems:722.4 ; Mathematics:921 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4

COMPUTER SCIENCE

Web of Science

1.Jinan Univ, Dept Comp Sci, Guangzhou, Guangdong, Peoples R China
2.Facebook Inc, 7006 126th Ave NE, Kirkland, WA 98033 USA
3.South Univ Sci & Technol China, Shenzhen, Peoples R China

Tan, Haisheng,Liang, Hongyu,Wang, Rui,et al. Computing Roman domatic number of graphs[J]. INFORMATION PROCESSING LETTERS,2016,116(9):554-559.

Tan, Haisheng,Liang, Hongyu,Wang, Rui,&Zhou, Jipeng.(2016).Computing Roman domatic number of graphs.INFORMATION PROCESSING LETTERS,116(9),554-559.

Tan, Haisheng,et al."Computing Roman domatic number of graphs".INFORMATION PROCESSING LETTERS 116.9(2016):554-559.