Graph universal cycles: Compression and connections to universal cycles
Graph universal cycles: Compression and connections to universal cycles
复制标题
图通用循环：压缩和与通用循环的连接
DOI：
10.1016/j.aam.2023.102522
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Elizabeth Sprangel
中科院分区：
文献类型：
--
作者：
R. Kirsch;Clare Sibley;Elizabeth Sprangel
普适循环，如德布鲁因循环，是符号的循环序列，它将来自某个族的每个组合对象作为一个连续的子序列精确地表示一次。图泛圈是2010年引入的泛圈的图模拟。我们引入图通用部分循环，一个更紧凑的表示图类，它使用“不知道”的边缘。我们展示了如何为标记图、阈值图和置换图构造图的泛部分环。对于阈值图和置换图，证明了图的泛圈和图的泛部分圈分别与泛圈和压缩泛圈密切相关.利用同样的联系，我们定义并证明了置换图泛圈的反重叠形式的存在性。我们还证明了无标号图的广义图泛圈的存在性。
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 ans-overlap form of graph universal cycles. We also prove the existence of a generalized form of graph universal cycles for unlabeled graphs.
影响因子：
1.1
作者：
Cantwell, Amelia;Geraci, Juliann;Godbole, Anant;Padilla, Cristobal
通讯作者：
Padilla, Cristobal
影响因子：
1.1
作者：
Kirsch, Rachel;Lidický, Bernard;Sibley, Clare;Sprangel, Elizabeth
通讯作者：
Sprangel, Elizabeth