On the k-tuple domination of de Bruijn and Kautz digraphs

被引：20

作者：

Araki, Toru ^{[1
]}

机构：

[1] Iwate Univ, Dept Comp & Informat Sci, Morioka, Iwate 0208551, Japan

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 104卷 / 03期

关键词：

k-tuple domination; de Bruijn digraph; Kautz digraph; interconnection networks;

D O I：

10.1016/j.ipl.2007.05.010

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u, v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：86 / 90

页数：5

共 22 条

[1]

Bermond J.-C., 1988, CONGR NUMER CONF J N, V66, P283

[2]

BERMOND JC, 1989, HYPERCUBE AND DISTRIBUTED COMPUTERS, P279

[3] Super link-connectivity of iterated line digraphs [J].

Cheng, XY ;

Du, XF ;

Min, MK ;

Ngo, HQ ;

Ruan, L ;

Sun, JH ;

Wu, WL .

THEORETICAL COMPUTER SCIENCE, 2003, 304 (1-3) :461-469

[4]

FIOL MA, 1984, IEEE T COMPUT, V33, P400, DOI 10.1109/TC.1984.1676455

[5]

Harary F, 2000, ARS COMBINATORIA, V55, P201

[6] Completely independent spanning trees in the underlying graph of a line digraph [J].

Hasunuma, T .

DISCRETE MATHEMATICS, 2001, 234 (1-3) :149-157

[7]

Haynes T. W., 1998, FUNDAMENTALS DOMINAT

[8] The bondage numbers of extended de Bruijn and Kautz digraphs [J].

Huang, Jia ;

Xu, Jun-Ming .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2006, 51 (6-7) :1137-1147

[9]

IMASE M, 1983, IEEE T COMPUT, V32, P782, DOI 10.1109/TC.1983.1676323

[10]

IMASE M, 1981, IEEE T COMPUT, V30, P439, DOI 10.1109/TC.1981.1675809

← 1 2 3 →