Search for Articles:

Contents

Castling tree of tight Dyck nests with applications to odd and middle-levels graphs

Italo J. Dejter1
1University of Puerto Rico, Rio Piedras, PR 00936-8377
Copyright © Italo J. Dejter. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A subfamily of Dyck words called tight Dyck words is seen to correspond, via a “castling” procedure, to the vertex set of an ordered tree T. From T, a “blowing” operation recreates the whole family ol Dyck words. The vertices of T can be elementarily updated all along T. This simplifies an edge-supplementary arc-factorization view of Hamilton cycles of odd and middle-levels graphs found by T. Mütze et al. This takes into account that the Dyck words represent: (a) the cyclic and dihedral vertex classes of odd and middle-levels graphs, respectively, and (b) the cycles of their 2-factors, as found by T. Mütze et al.

Keywords: Dyck words, ordered trees, Hamilton cycles