Twin Domination Problems in Round Digraphs

Tamaki NAKAJIMA  Yuuki TANAKA  Toru ARAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1192-1199
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1192
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
twin domination,  digraphs,  round digraphs,  locally semicomplete digraphs,  

Full Text: PDF>>
Buy this Article



Summary: 
A twin dominating set of a digraph D is a subset S of vertices if, for every vertex u ∉ S, there are vertices x,y ∈ S such that ux and yu are arcs of D. A digraph D is round if the vertices can be labeled as v0,v1,...,vn-1 so that, for each vertex vi, the out-neighbors of vi appear consecutively following vi and the in-neighbors of vi appear consecutively preceding vi. In this paper, we give polynomial time algorithms for finding a minimum weight twin dominating set and a minimum weight total twin dominating set for a weighted round digraph. Then we show that there is a polynomial time algorithm for deciding whether a locally semicomplete digraph has an independent twin dominating set. The class of locally semicomplete digraphs contains round digraphs as a special case.