Hamiltonicity of large generalized de Bruijn cycles

Description

In this article, we determine when the large generalized de Bruijn cycles BGC(p, d, n) are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized p-cycles. They are the Kronecker product of the generalized de Bruijn digraph GB(d, n) and the dicycle of length p, where GB(d, n) is the digraph whose vertices are labeled with the integers modulo n such that there is an arc from vertex i to vertex j if, and only if, j ≡ di + α (mod n), for every α with 0 ≤ α ≤ d − 1.

Abstract

International audience

Additional details