Graph universal cycles: compression and connections to universal cycles

DOI10.1016/J.AAM.2023.102522MaRDI QIDQ6044313zbMATH OpenOpenAlexFDO

Authors Rachel Kirsch, Clare Sibley, Elizabeth Sprangel

Publication date 17 May 2023

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph universal partial cyclesunlabeled graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: Universal cycles, such as De Bruijn cycles, are cyclic sequences of symbols that represent every combinatorial object from some family exactly once as a consecutive subsequence. Graph universal cycles are a graph analogue of universal cycles introduced in 2010. We introduce graph universal partial cycles, a more compact representation of graph classes, which use "do not know" edges. We show how to construct graph universal partial cycles for labeled graphs, threshold graphs, and permutation graphs. For threshold graphs and permutation graphs, we demonstrate that the graph universal cycles and graph universal partial cycles are closely related to universal cycles and compressed universal cycles, respectively. Using the same connection, for permutation graphs, we define and prove the existence of an $s$-overlap form of graph universal cycles. We also prove the existence of a generalized form of graph universal cycles for unlabeled graphs.

Recommendations

• Graph universal cycles of combinatorial objects
• Universal cycles of complementary classes
• Equivalence class universal cycles for permutations
• Universal cycles for combinatorial structures

Cites work

• s-overlap cycles for permutations
• Binary de Bruijn partial words with one hole
• Graph universal cycles of combinatorial objects
• scientific article; zbMATH DE number 3864496 (Why is no real title available?)
• scientific article; zbMATH DE number 1735659 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• Multi de Bruijn sequences
• On -overlap graphs
• On shortening u-cycles and u-words for permutations
• On Unicursal Paths in a Network of Degree 4
• On universal cycles of labeled graphs
• On universal partial words
• On Universal Threshold Graphs
• Shortened universal cycles for permutations
• Threshold graphs and related topics
• Universal cycles for combinatorial structures
• Universal cycles for permutation classes
• Universal cycles for permutations
• Universal partial words over non-binary alphabets

Cited in

(5)

• Compressions, graphs, and hyperreflexivity
• On universal cycles of labeled graphs
• Graph cores via universal completability
• scientific article; zbMATH DE number 1262802 (Why is no real title available?)
• Universal partial tori

This page was built for publication: Graph universal cycles: compression and connections to universal cycles

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