𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the number of cycles of short length in the DE Bruijn-good graph Gn

✍ Scribed by Zhe-xian Wan; Rong-hua Xiong; Min-an Yu

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
865 KB
Volume
62
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

An algebraic approach to enumerate the number of cycles of short length in the de Bruijn-Good graph Gn is given and the following theorem is proved.

where ~)k,m--1 is defined to be the number of positive integers l <<-k satisfying (k, l) <<-m -1, l~(q) is the M6bius function, dt = (k, l), e~ = 0 or j -1 according as j = 0 or j > O, and fl(k, k) = 1/ k Edlk p(d)2 k/a.

πŸ“œ SIMILAR VOLUMES

On the number of cycles of length 4 in a
On the number of cycles of length 4 in a maximal planar graph
✍ Ahmad Fawzi Alameddine πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 148 KB πŸ‘ 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ β‰₯

On the number of cycles of length k in a
On the number of cycles of length k in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 723 KB

Let G be a maximal planar graph with p vertices, and let Ck(G) denote the number of cycles of length k in G. We first present tight bounds for C,(G) and C,(G) in terms of p. We then give bounds for Ck(G) when 5 5 k 5 p , and consider in particular bounds for C,(G), in terms of p. Some conjectures an

On the distribution of cycle lengths in
On the distribution of cycle lengths in graphs
✍ A. GyΓ‘rfΓ‘s; J. KomlΓ³s; E. SzemerΓ©di πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 843 KB

The set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdos and Hajnal stating that for suit

On the maximum number of cycles in a pla
On the maximum number of cycles in a planar graph
✍ R. E. L. Aldred; Carsten Thomassen πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__β€‰βˆ’β€‰__p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__β€‰βˆ’β€‰1^ = __o__(2^__r__β€‰βˆ’β€‰1^) cycles. The planar result is best possib

On the number of hamilton cycles in a ra
On the number of hamilton cycles in a random graph
✍ C. Cooper; A. M. Frieze πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 576 KB

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n)('-')" distinct hamilton cycles for any fixed E > 0.