Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647074 | Discrete Mathematics | 2015 | 5 Pages |
Abstract
A twin dominating set in a digraph D=(V,A)D=(V,A) is a set S⊆VS⊆V such that, for every w∈V∖Sw∈V∖S, there exist arcs (u,w),(w,v)∈A(u,w),(w,v)∈A with u,v∈Su,v∈S. A twin dominating set SS is efficient if there is no arc in the subdigraph induced by SS and, for every w∈V∖Sw∈V∖S, there exist exactly one vertex u∈Su∈S and exactly one vertex v∈Sv∈S such that arcs (u,w),(w,v)∈A(u,w),(w,v)∈A. This paper resolves a conjecture regarding an efficient twin domination set in generalized De Bruijn digraphs. The conjecture says that the generalized De Bruijn digraphs GB(n,d)GB(n,d) with nn a multiple of d+1d+1 have an efficient twin dominating set if and only if dd is even and relatively prime to nn. This paper affirms this conjecture.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yue-Li Wang,