کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650398 1342486 2008 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A construction of Gray codes inducing complete graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A construction of Gray codes inducing complete graphs
چکیده انگلیسی

A binary Gray code G(n)G(n) of length nn, is a list of all 2n2nnn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n)G(n), denoted by S(n)≔s1,s2,…,s2n-1S(n)≔s1,s2,…,s2n-1, is called the transition sequence of the Gray code G(n)G(n). The graph GG(n)GG(n) induced by a Gray code G(n)G(n) has vertex set {1,2,…,n}{1,2,…,n} and edge set {{si,si+1}:1⩽i⩽2n-2}{{si,si+1}:1⩽i⩽2n-2}. If the first and the last codeword differ only in position s2ns2n, the code is cyclic and we extend the graph by two more edges {s2n-1,s2n}{s2n-1,s2n} and {s2n,s1}{s2n,s1}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585–598] about a construction of an nn-bit Gray code inducing the complete graph KnKn. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 18, 28 September 2008, Pages 4124–4132
نویسندگان
, ,