Hamiltonian cycles on commutative-step and fixed-step networks.

Autores: Miguel Ángel Fiol Mora , José Luis Andrés Yebra
Localización: Stochastica: revista de matemática pura y aplicada, ISSN 0210-7821, Vol. 12, Nº. 2-3, 1988, págs. 113-129
Idioma: español
Títulos paralelos:
- Ciclos de Hamilton en redes de paso conmutativo y de paso fijo.
Enlaces
- Texto completo (pdf)
Resumen
- From a natural generalization to Z2 of the concept of congruence, it is possible to define a family of 2-regular digraphs that we call commutative-step networks. Particular examples of such digraphs are the cartesian product of two directed cycles, C1 x Ch, and the fixed-step network (or 2-step circulant digraph) DN,a,b.
  
  In this paper the theory of congruences in Z2 is applied to derive three equivalent characterizations of those commutative-step networks that have a Hamiltonian cycle. Some known results are then obtained as a corollary. For instance, necessary and sufficient conditions for C1 x Ch or DN,a,b to be hamiltonian are discussed.