On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs

被引：31

作者：

Kikuchi, Y ^{[1
]}

Shibata, Y ^{[1
]}

机构：

[1] Gunma Univ, Dept Comp Sci, Kiryu, Gumma 3768515, Japan

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 02期

关键词：

generalized de Bruijn digraphs; generalized Kautz digraphs; dominating set; domination number; absorbant; kernel; interconnection networks;

D O I：

10.1016/S0020-0190(02)00479-9

中图分类号：

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

学科分类号：

0812 ;

摘要：

This work deals with the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. Dominating sets for digraphs are not familiar compared with dominating sets for undirected graphs. Whereas dominating sets for digraphs have more applications than those for undirected graphs. We construct dominating sets of generalized de Bruijn digraphs where obtained dominating sets have some qualifications. For generalized Kautz digraphs, there is a minimum dominating set in those constructed dominating sets. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：79 / 85

页数：7

共 17 条

[1] DOMINATION AND INDEPENDENT DOMINATION NUMBERS OF A GRAPH [J].

ALLAN, RB ;

LASKAR, R .

DISCRETE MATHEMATICS, 1978, 23 (02) :73-76

[2]

[Anonymous], HYPERCUBE DISTRIBUTE

[3]

BARKAUSKAS AE, 1993, C NUMER, V98, P27

[4] COMPLEXITY OF FINDING K-PATH-FREE DOMINATING SETS IN GRAPHS [J].

BARYEHUDA, R .

INFORMATION PROCESSING LETTERS, 1982, 14 (05) :228-232

[5] COMBINATORIAL PROBLEM IN LOGIC [J].

BERGE, C ;

RAO, AR .

DISCRETE MATHEMATICS, 1977, 17 (01) :23-26

[6] KERNELS IN DIRECTED-GRAPHS - A POISON GAME [J].

DUCHET, P ;

MEYNIEL, H .

DISCRETE MATHEMATICS, 1993, 115 (1-3) :273-276

[7]

FISHER D, 1995, C NUMER, V108, P97

[8] COMPLEXITY OF PROBLEMS IN GAMES, GRAPHS AND ALGEBRAIC EQUATIONS [J].

FRAENKEL, AS ;

YESHA, Y .

DISCRETE APPLIED MATHEMATICS, 1979, 1 (1-2) :15-30

[9]

Ghoshal J, 1998, MG TXB PUR APPL MATH, V209, P401

[10]

Haynes T. W., 1998, FUNDAMENTALS DOMINAT

← 1 2 →