Enumerating cycles in the graph of overlapping permutations

DOI10.1016/J.DISC.2017.09.010zbMATH Open1376.05070arXiv1609.02210OpenAlexW2964139813MaRDI QIDQ1685994FDOQ1685994

Authors: John Asplund, N. Bradley Fox 

Publication date: 20 December 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

cyclesclosed walksoverlapping permutations

Mathematics Subject Classification ID

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

Cites Work

• Patterns in permutations and words.
• Universal cycles for combinatorial structures
• \(s\)-overlap cycles for permutations
• Title not available (Why is that?)
• Universal cycles for permutations
• On uniquely \(k\)-determined permutations
• Number of cycles in the graph of 312-avoiding permutations

Cited In (8)

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

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)