zbMATH — the first resource for mathematics

Enumerating cycles in the graph of overlapping permutations. (English) Zbl 1376.05070
Summary: 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 \cdots a_{n+1}\) would connect the standardization of \(a_1 \cdots a_n\) to the standardization of \(a_2\cdots 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.

05C30 Enumeration in graph theory
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI arXiv
[1] Avgustinovich, S.; Kitaev, S., On uniquely \(k\)-determined permutations, Discrete Math., 308, 1500-1507, (2008) · Zbl 1134.05002
[2] Chung, F.; Diaconis, P.; Graham, R., Universal cycles for combinatorial structures, Discrete Math., 110, 1-3, 43-59, (1992) · Zbl 0776.05001
[3] Ehrenborg, R.; Kitaev, S.; Steingr√≠msson, E., Number of cycles in the graph of 312-avoiding permutations, J. Combin. Theory Ser. A, 129, 1-18, (2015) · Zbl 1302.05081
[4] Golomb, S., Shift Register Sequences, (1967), Holden-Day, Inc. San Francisco
[5] Horan, V.; Hurlbert, G., \(s\)-overlap cycles for permutations, Bull. Inst. Combin. Appl., 69, 60-67, (2013) · Zbl 1321.05005
[6] Johnson, J. R., Universal cycles for permutations, Discrete Math., 309, 5264-5270, (2009) · Zbl 1181.05005
[7] Kitaev, S., Patterns in Permutations and Words, (2011), Springer-Verlag Berlin Heidelberg · Zbl 1257.68007
[8] West, D. B., Introduction to Graph Theory, Vol. 2, (2001), Prentice Hall Upper Saddle River
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.