On universal cycles of labeled graphs

zbMATH Open1184.05110arXiv0808.3610MaRDI QIDQ2380435FDOQ2380435

Authors: Greg Brockman, Bill Kay, Emma E. Snively 

Publication date: 26 March 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A universal cycle is a compact listing of a class of combinatorial objects. In this paper, we prove the existence of universal cycles of classes of labeled graphs, including simple graphs, trees, graphs with m edges, graphs with loops, graphs with multiple edges (with up to m duplications of each edge), directed graphs, hypergraphs, and k-uniform hypergraphs.

Full work available at URL: https://arxiv.org/abs/0808.3610

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Graph universal cycles: compression and connections to universal cycles
• On universal cycles for new classes of combinatorial structures
• Universal cycles of complementary classes
• Graph universal cycles of combinatorial objects
• Universal cycles for combinatorial structures

zbMATH Keywords

arc digraphlabeled graphsuniversal cyclede Bruijn cycles

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (11)

• Binary bubble languages and cool-lex order
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Universal cycles of restriced words
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Universal and overlap cycles for posets, words, and juggling patterns
• Graph universal cycles of combinatorial objects
• Constructing the first (and coolest) fixed-content universal cycle
• Graph universal cycles: compression and connections to universal cycles
• On universal cycles for new classes of combinatorial structures
• Solution of an outstanding conjecture: the non-existence of universal cycles with \(k=n-2\)
• Shortened universal cycles for permutations

This page was built for publication: On universal cycles of labeled graphs

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