Multicover Ucycles

DOI10.1016/0012-365X(95)91427-RMaRDI QIDQ1343787zbMATH OpenOpenAlexWikidataFDO

Authors Glenn H. Hurlbert

Publication date 2 July 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(95)91427-r

zbMATH Keywords

\(t\)-cover Ucycleuniversal cycle

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A universal cycle, or Ucycle, for \(k\)-subsets of \([n]= \{1,2,\dots, n\}\) is a cyclic sequence of \((\begin{smallmatrix} n\\ k\end{smallmatrix})\) integers with the property that every \(k\)-subsets of \([n]\) appears exactly once consecutively in the sequence. A \(t\)-cover Ucycle for \(k\)-subsets of \([n]\) is a cyclic sequence of \(t(\begin{smallmatrix} n\\ k\end{smallmatrix})\) integers with the property that every \(k\)-subset of \([n]\) appears exactly \(t\)-times consecutively in the sequence. The author investigates the minimal number \(t= U(n, k)\) for which there is a \(t\)-cover Ucycle. For example: (a) \(U(n, 4)\leq 2\) if \(n\equiv 2\pmod 4\). (b) \(U(n,5)\leq 2\) if \(n\geq 16\) is relatively prime to 5 and \(n\not\equiv 2\pmod 3\).

Recommendations

• scientific article; zbMATH DE number 5809
• Totally multicoloured cycles
• Generalized bicycles
• STACS 2005
• Cycle double covers and the semi-Kotzig frame
• Multicoloured Hamilton cycles
• Acyclic covers
• Cycles of covers

Cites work

• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Notes on Binomial Coefficients I-A Generalization of Lucas' Congruence†
• On Universal Cycles for k-Subsets of an n-Set
• Universal cycles for combinatorial structures
• Universal cycles of k-subsets and k-permutations

Cited in

(5)

• Universal cycles of \((n - 1)\)-partitions of an \(n\)-set
• Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences
• Near-universal cycles for subsets exist
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• Universal and near-universal cycles of set partitions

This page was built for publication: Multicover Ucycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1343787)