A construction of Gray codes inducing complete graphs |
| |
Authors: | I Nengah Suparta |
| |
Institution: | a Department of Mathematics, Faculty of Mathematics and Natural Sciences, Ganesha University of Education, Jalan Udayana Singaraja, 81116 Bali, Indonesia b Department of Mathematics, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands |
| |
Abstract: | A binary Gray code G(n) of length n, is a list of all 2nn-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), denoted by S(n)?s1,s2,…,s2n-1, is called the transition sequence of the Gray code G(n). The graph GG(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{si,si+1}:1?i?2n-2}. If the first and the last codeword differ only in position s2n, the code is cyclic and we extend the graph by two more edges {s2n-1,s2n} and {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 n-bit Gray code inducing the complete graph Kn. 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]. |
| |
Keywords: | Gray code Complete graph |
本文献已被 ScienceDirect 等数据库收录! |
|