On regular configurations and disjoint cycles in shift graphs

arXiv0710.0125MaRDI QIDQ6206967FDOQ6206967

Publication date: 30 September 2007

Abstract: Configurations are necklaces with prescribed numbers of red and black beads. Among all possible configurations, the regular one plays an important role in many applications. In this paper, several aspects of regular configurations are discussed, including construction, uniqueness, symmetry group and the link with balanced words. Another model of configurations is the polygons formed by a given number of sides of two different lengths. In this context, regular configurations are used to obtain a lower bound for the cycles packing number of shift graphs, a subclass of the directed circulant graphs.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) General topics in the theory of algorithms (68W01)

This page was built for publication: On regular configurations and disjoint cycles in shift graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206967)