Enumerating cycles in the graph of overlapping permutations.

*(English)*Zbl 1376.05070Summary: 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 |

##### 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 |

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.