✦ LIBER ✦

Counting small cycles in generalized de Bruijn digraphs

✍ Scribed by Hasunuma, Toru; Shibata, Yukio

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 143 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199701)29:1<39::aid-net4>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

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 ͚ l Ék m(k/l)g l d l / g l  , where m is the Mo ¨bius function and r denotes the smallest integer not smaller than a real number r.

📜 SIMILAR VOLUMES

Generating and Counting Hamilton Cycles

Generating and Counting Hamilton Cycles in Random Regular Graphs

✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ž . with vertex set n . We describe polynomial time algorithms that whp i find a Ž . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

Cycles through Large Degree Vertices in

Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem

✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every

Density-dependent Prenatal Androgen Expo

Density-dependent Prenatal Androgen Exposure as an Endogenous Mechanism for the Generation of Cycles in Small Mammal Populations

✍ Lindsay G. Cowell; Larry B. Crowder; Thomas B. Kepler 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 270 KB

Small mammal populations exhibit cyclic fluctuations in their population densities. Several hypotheses regarding the mechanisms underlying these population cycles have been advanced, but none has yet gained general approval. We propose here an endogenous mechanism based on the masculinization of fem

Simultaneous analysis of a series of pho

Simultaneous analysis of a series of phosphorylated sugars in small tissue samples by anion exchange chromatography and pulsed amperometric detection

✍ Steef M. de Bruijn; Richard G. F. Visser; Dr. Dick Vreugdenhil 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 79 KB

A simple method was developed to analyse a series of phosphorylated sugars in small physiological samples with dry tissue weights as low as 10 mg. Phosphorylated compounds were extracted from the tissue after boiling in 80% methanol by re-suspension of the dried methanol phase in water. The sugar ph