论文标题
图形通用周期：压缩和连接到通用周期
Graph Universal Cycles: Compression and Connections to Universal Cycles
论文作者
论文摘要
通用循环（例如de bruijn循环）是符号的环状序列，它们代表了一个连续的子序列，代表了一次来自某个家庭的每个组合对象。图形通用周期是2010年引入的通用周期的图形类似物。我们介绍了图形通用部分循环，这是图形类别的更紧凑的表示，使用“不知道”边缘。我们展示了如何为标记的图形，阈值图和置换图构造图形通用部分循环。对于阈值图和置换图，我们证明了图表通用周期和图表通用部分循环分别与通用循环和压缩通用循环密切相关。使用相同的连接，对于置换图，我们定义并证明了图形通用周期的$ S $跨曲线形式。我们还证明了用于未标记图的普遍形式的图形通用循环的存在。
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.
