✦ LIBER ✦

Cayley Digraphs from Complete Generalized Cycles

✍ Scribed by J.M. Brunat; M. Espona; M.A. Fiol; O. Serra

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 227 KB
Volume: 20
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1999.0290

No coin nor oath required. For personal study only.

✦ Synopsis

The complete generalized cycle G (d, n) is the digraph which has Z n × Z d as the vertex set and every vertex (i, x) is adjacent to the d vertices (i + 1, y) with y ∈ Z d . As a main result, we give a necessary and sufficient condition for the iterated line digraph G(d, n, k) = L k-1 G(d, n), with d a prime number, to be a Cayley digraph in terms of the existence of a group d of order d and a subgroup N of ( d ) n isomorphic to ( d ) k . The condition is shown to be also sufficient for any integer

By using some properties of the homogeneous linear recurrences in finite rings, necessary and sufficient conditions for G (d, n, k) to be an R-Cayley digraph are obtained. As a consequence, when R = Z d a new characterization for the digraphs G (d, n, k) to be Z d -Cayley digraphs is derived. As a corollary, sufficient conditions for the corresponding underlying graphs to be Cayley can be deduced. If d is a prime power and F d is a finite field of order d, the digraphs G(d, n, k) which are F d -Cayley digraphs are in 1-1 correspondence with the cyclic (n, k)-linear codes over F d .

📜 SIMILAR VOLUMES

Isomorphic factorization of the complete

Isomorphic factorization of the complete graph into Cayley digraphs

✍ G. L. Chia; Poh-Hwa Ong 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract Let __Z__~__p__~ denote the cyclic group of order __p__ where __p__ is a prime number. Let __X__ = __X__(__Z__~__p__~, __H__) denote the Cayley digraph of __Z__~__p__~ with respect to the symbol __H__. We obtain a necessary and sufficient condition on __H__ so that the complete graph on

Unilaterally connected large digraphs an

Unilaterally connected large digraphs and generalized cycles

✍ José Gómez; Eduardo A. Canale; Xavier Muñoz 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract Lower and upper bounds on the order of digraphs and generalized __p__‐cycles with a specified maximum degree and unilateral diameter are given for generic values of the parameters. Infinite families of digraphs attaining the bounds asymptotically or even exactly are presented. In partic

Hamiltonian cycles and paths in Cayley g

Hamiltonian cycles and paths in Cayley graphs and digraphs — A survey

✍ Stephen J. Curran; Joseph A. Gallian 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 927 KB

Cayley graphs arise naturally in computer science, in the study of word-hyperbolic groups and automatic groups, in change-ringing, in creating Escher-like repeating patterns in the hyperbolic plane, and in combinatorial designs. Moreover, Babai has shown that all graphs can be realized as an induced

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

Hamiltonian paths in Cayley digraphs of

Hamiltonian paths in Cayley digraphs of finitely-generated infinite abelian groups

✍ Douglas Jungreis 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 983 KB

We show every finitely-generated, infinite abeliar\_ group (i.e. Zn x G where G is a finite abelian group) has a minimal generating set for which the Cayley digraph has a two-way in&rite hamiltonian path, and if n 2 2, then this Cayley digraph also has a one-way infinite hamiltonian path. We show fu

On complete strongly connected digraphs

On complete strongly connected digraphs with the least number of 3-cycles

✍ M. Burzio; J. Pelant 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 186 KB

The least number of 3-cycles (cycles of length 3) that a hamiltonian tournament of order n can contain is n -2 (see [3]). Since each complete strongly connected digraph contains a spanning hamiltonian subtournament (see [2]), n-2 is also the least number of 3-cycles for these digraphs. In this pape