We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Some classes of bipartite graphs induced by Gray codes.
- Authors
Suparta, I. Nengah
- Abstract
A Gray code of length n is a list of all binary words of length n such that each two successive codewords differ in only one bit position. If the first and the last codewords also share this property, the Gray code is called cyclic, otherwise it is called non-cyclic. The numbers indicating bit positions in where two successive codewords differ in the list of Gray codes are called transition numbers, and the sequence of these all numbers is called the transition sequence of the Gray code. In this article, bit positions of a Gray code of length n will be counted from 1 up until n. If a graph with vertex set f1; 2; :::; ng having the property that two vertices i and j are adjacent in the graph if and only if, i and j are consecutive transitions in the transition sequence of a Gray code, then the graph is called induced by the Gray code. Some classes of bipartite graphs are shown to be induced by Gray codes. Particularly, we show that complete bipartite graphs are induced by Gray codes.
- Subjects
BIPARTITE graphs; GRAY codes; HAMILTON'S equations; HAMILTONIAN operator; CONCATENATED codes
- Publication
Electronic Journal of Graph Theory & Applications, 2017, Vol 5, Issue 2, p312
- ISSN
2338-2287
- Publication type
Article
- DOI
10.5614/ejgta.2017.5.2.12