Minimum 2-tuple dominating set of permutation graphs |
| |
Authors: | Sambhu Charan Barman Sukumar Mondal Madhumangal Pal |
| |
Institution: | 1. Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, 721 102, India 2. Department of Mathematics, Raja N.L. Khan Women’s College, Gope Palace, Midnapore, 721 102, India
|
| |
Abstract: | For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ ×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D 2 is said to be minimal if there does not exist any D′?D 2 such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D 2, denoted by γ ×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n 2) time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|