Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On Universal Cycles of Labeled Graphs. | On Universal Cycles of Labeled Graphs Greg Brockman Harvard UNivERSiTy Cambridge ma 02138 United States brockman@ Bill Kay UNiVERSiTy OF South Carolina Columbia sc 29208 United States kayw@ .edu Emma E. Snively Rose-Hulman Institute of TECHNOLOGy Terre Haute in 47803 United States snivelee@ Submitted Aug 26 2008 Accepted Dec 14 2009 Published Jan 5 2010 Mathematics Subject Classification 05C30 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. 1 Introduction A simple example of a universal cycle U-cycle is the cyclic string 11101000 which contains every 3-letter word on a binary alphabet precisely once. We obtain these words by taking substrings of length 3 it is useful to imagine that we are looking at the string through a window of length 3 and we shift the window to transition from one word to the next allowing the window to wrap if necessary. Universal cycles have been shown to exist for words of any length and for any alphabet size. For the special case of a binary alphabet such strings are also known as de Bruijn cycles . The concept easily lends itself to extension and universal cycles for permutations partitions and certain classes of functions are well-studied in the literature see Chung Diaconis Graham 1 for an overview of previous work in the field . In all cases the distinguishing feature of a universal cycle is that by shifting a window through a cyclic THE electronic journal of combinatorics 17 2010 R4 1 string or in some generalizations an array all objects in a given class are represented precisely once. In this paper we generalize the notion of universal cycles. In particular we show that these cycles .
