Enumerating cycles in the graph of overlapping permutations. (English) Zbl 1376.05070

Asplund, John; Fox, N. Bradley

Discrete Math. 341, No. 2, 427-438 (2018).

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.

MSC:

05C30	Enumeration in graph theory
05C38	Paths and cycles
05C20	Directed graphs (digraphs), tournaments

Keywords:

overlapping permutations; cycles; closed walks

References:

[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