"Graph Universal Cycles of Combinatorial Objects" by Amelia Cantwell, Juliann Geraci et al.
 

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.

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 4
  • Usage
    • Abstract Views: 11
  • Captures
    • Readers: 1
see details

Share

COinS