Enumerating cycles in the graph of overlapping permutations

DOI10.1016/J.DISC.2017.09.010MaRDI QIDQ1685994zbMATH OpenOpenAlexFDO

Authors John Asplund, N. Bradley Fox

Publication date 20 December 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.02210

zbMATH Keywords

cyclesclosed walksoverlapping permutations

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Number of cycles in the graph of 312-avoiding permutations
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Number of cycles in the graph of 312-avoiding permutations
• \(s\)-overlap cycles for permutations
• Overlap cycles for permutations: necessary and sufficient conditions

Cites work

• scientific article; zbMATH DE number 3422259 (Why is no real title available?)
• Number of cycles in the graph of 312-avoiding permutations
• On uniquely \(k\)-determined permutations
• Patterns in permutations and words.
• Universal cycles for combinatorial structures
• Universal cycles for permutations
• \(s\)-overlap cycles for permutations

Cited in

(8)

• Adjacent \(q\)-cycles in permutations
• Number of cycles in the graph of 312-avoiding permutations
• \(s\)-overlap cycles for permutations
• Overlap cycles for permutations: necessary and sufficient conditions
• Number of cycles in the graph of 312-avoiding permutations
• Cycles in the graph of overlapping permutations avoiding barred patterns
• The feasible region for consecutive patterns of permutations is a cycle polytope
• The feasible region for consecutive patterns of permutations is a cycle polytope

This page was built for publication: Enumerating cycles in the graph of overlapping permutations

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