Gray codes faulting matchings

Riste Skrekovski
University of Ljubljana


Abstract:

A (cyclic) n-bit Gray code is a (cyclic) ordering of all $2^n$ binary strings of length n such that consecutive strings differ in a single bit. Equivalently, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Q_n, and a cyclic Gray code as a Hamiltonian cycle of Q_n. In this talk we study Hamiltonian paths and cycles of Q_n avoiding a given set of faulty edges that form a matching, briefly called (cyclic) Gray codes faulting a given matching.

Retour au séminaire