✦ LIBER ✦

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

✍ Scribed by Yosuke Kikuchi; Yukio Shibata

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 94 KB
Volume: 86
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00479-9

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Generalized de Bruijn digraphs

✍ D. Z. Du; F. K. Hwang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 566 KB

We show that the digraphs proposed independently by lmase and Itoh, and Reddy, Radhan and Kuhl to minimize diameters essentially retain all the nice properties of de Bruijn digraphs and yet are applicable to any number of nodes. In particular we give results on the number of loops, the link connecti

The total domination and total bondage n

The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs

✍ Jia Huang; Jun-Ming Xu 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 218 KB

The Hamiltonian property of generalized

The Hamiltonian property of generalized de Bruijn digraphs

✍ D.Z Du; D.F Hsu; F.K Hwang; X.M Zhang 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 512 KB

Counting small cycles in generalized de

Counting small cycles in generalized de Bruijn digraphs

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

In this paper, we count small cycles in generalized de Bruijn digraphs. Let n Å pd h , where d É / p, and g l Å gcd(d l 0 1, n). We show that if p õ d 3 and k °log d n / 1, or p ú d 3 and k °h / 3, then the number of cycles of length k in a generalized de Bruijn digraph G B (n, d) is given by 1/ k

A note on recursive properties of the de

A note on recursive properties of the de Bruijn, Kautz and FFT digraphs

✍ M.C Heydemann; D Sotteau 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 437 KB

On even factorizations and the chromatic

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

✍ Jean-Claude Bermond Cnrs; Pavol Hell 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB

## Abstract Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree __d__ have arc‐chromatic index __2d__. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spann