𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Feedback numbers of de Bruijn digraphs

✍ Scribed by Xirong Xu; Yongchang Cao; Jun-Ming Xu; Yezhou Wu

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
586 KB
Volume
59
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

A subset of vertices of a graph G is called a feedback vertex set of G if its removal results in an acyclic subgraph. Let f (d, n) denote the minimum cardinality over all feedback vertex sets of the de Bruijn digraph B (d, n). This paper proves that for any integers d β‰₯ 2 and n β‰₯ 2

where i | n means i divides n, and Ο•(i) is the Euler totient function.

πŸ“œ SIMILAR VOLUMES

Generalized de Bruijn digraphs
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

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