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.
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-10840 |
Date | 01 June 2021 |
Creators | Cantwell, Amelia, Geraci, Juliann, Godbole, Anant, Padilla, Cristobal |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0016 seconds