Title
Graph Universal Cycles of Combinatorial Objects
Document Type
Article
Publication Date
6-1-2021
Description
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 C5 with edge set consisting of {2,3} and {5,1}, namely the “second” and “fifth” edges in C5. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.
Citation Information
Cantwell, Amelia; Geraci, Juliann; Godbole, Anant; and Padilla, Cristobal. 2021. Graph Universal Cycles of Combinatorial Objects. Advances in Applied Mathematics. Vol.127 https://doi.org/10.1016/j.aam.2021.102166 ISSN: 0196-8858