Enumerating cycles in the graph of overlapping permutations

摘要

The graph of overlapping permutations is a directed graph that is an analogue to the De Bruijn graph. It consists of vertices that are permutations of length n and edges that are permutations of length n+1 in which an edge a(1) ... a(n+1) would connect the standardization of a(1)...a(n) to the standardization of a(2) ... a(n+1). We examine properties of this graph to determine where directed cycles can exist, to count the number of directed 2-cycles within the graph, and to enumerate the vertices that are contained within closed walks and directed cycles of more general lengths. (C) 2017 Elsevier B.V. All rights reserved.