Graph universal cycles of combinatorial objects
Graph universal cycles of combinatorial objects
复制标题
组合对象的通用循环图
DOI：
10.1016/j.aam.2021.102166
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Padilla, Cristobal
中科院分区：
文献类型：
--
作者：
Cantwell, Amelia;Geraci, Juliann;Godbole, Anant;Padilla, Cristobal
一个连通有向图，其中任何顶点的入度等于它的出度是欧拉的;这个基线结果被用作几个组合对象的泛圈（也称为U圈或广义德布鲁恩圈或U-圈）存在性证明的基础。优循环的存在通常依赖于我们对组合对象使用的特定表示。例如，我们是否应该将{1，2，3，4，5}的子集{2，5}表示为线性字符串中的“25”？第52章“可以接受吗？”或者使用{0，1，0，0，1}在战术上是有利的（并且是可以接受的）？在本文中，我们将组合对象表示为图，如[3]中所示，并展示了这种表示的灵活性和能力，以产生n-集的k-子集的图通用循环或Gucycles;[n]={1，2，...，n}的排列（和排列类），以及n-集的分区，从而重新访问[5]中首次研究的类。在这个图的框架下，我们将{2，5}表示为C5的子图A，其边集由{2，3}和{5，1}组成，即C5中的“第二”和“第五”边.排列通过它们的排列图表示，并且通过完全图的不相交并来设置划分。
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset {2, 5} of {1, 2, 3, 4, 5} as “25” in a linear string? Is the representation “52” acceptable? Or is it tactically advantageous (and acceptable) to go with {0, 1, 0, 0, 1}? In this paper, we represent combinatorial objects as graphs, as in [3], and exhibit the flexibility and power of this representation to produce graph universal cycles, or Gucycles, for k-subsets of an n-set; permutations (and classes of permutations) of [n]={1, 2,…, n}, and partitions of an n-set, thus revisiting the classes first studied in [5]. Under this graphical scheme, we will represent {2, 5} as the subgraph A of C 5 with edge set consisting of {2, 3} and {5, 1}, namely the “second” and “fifth” edges in C 5. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.
登录
查看更多内容
弱订单的通用循环
影响因子：
0.8
作者：
Victoria Horan;G. Hurlbert
通讯作者：
G. Hurlbert
在 [n] 的 k 子集上构造通用循环的归纳方法
影响因子：
0.7
作者：
Yevgeniy Rudoy
通讯作者：
Yevgeniy Rudoy
影响因子：
0.8
作者：
Antonio Blanca;A. Godbole
通讯作者：
A. Godbole
对德布鲁因循环理论的贡献
影响因子：
--
作者：
Andre A Campbell;A. Godbole;Bill Kay
通讯作者：
Bill Kay