Electronic Journal of Graph Theory and Applications 5 (2) (2017), 312–324

Some classes of bipartite graphs induced by Gray
codes
I Nengah Suparta
Faculty of Mathematics and Natural Sciences, Universitas Pendidikan Ganesha,
Jalan Udayana 11 Singaraja 81116 Bali, Indonesia
nengah.suparta@undiksha.ac.id

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 {1, 2, ..., n} 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.
Keywords: bipartite graph, complete bipartite graph, graph of transition, Gray code, Hamiltonian path, Hamiltonian cycle
Mathematics Subject Classification : 05C45
DOI:10.5614/ejgta.2017.5.2.12

1. Introduction
A Gray code of length n, or shortly an n-bit Gray code, is a list of all binary codewords of
length n such that any two successive codewords differ in only one bit position. If this property
holds for the last and first codewords in the list, the Gray code is called cyclic. Gray codes of
Received: 13 February 2017,

Revised: 14 August 2017,

312

Accepted: 10 September 2017.

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

length n can be considered as Hamiltonian paths on the hypercube graphs Qn , and cyclic Gray
codes correspond to Hamiltonian cycles. There will be of N = 2n n-bit codewords in Gray codes
of length n, and in this article these codewords will be indexed from 0 to N −1. Codeword of index
i will be denoted by xi , 0 ≤ i ≤ N − 1, and for cyclic Gray codes, indexes 0 and N are identified.
The transition sequence S(n) = s1 , s2 , ..., sN −1 , of an n-bit Gray code G(n) lists the bit positions
si ∈ [n] = {1, 2, ..., n} where xi−1 and xi differ. If G(n) is a cyclic Gray code, then the cyclic
transition sequence S(n) of G(n) is the concatenated sequence S(n), sN = s1 , s2 , ..., sN −1 , sN ,
where sN is the bit position where the codewords xN −1 and x0 differ. We occasionally call sN as
the closing transition of S(n). The number of transitions in a sequence will be called the length
of the sequence. Especially for the standard Gray code of length n, n ≥ 1, we denote its cyclic
transition sequence by S st (n) and it is defined as
S st (n) = Sst (n), n, for all integers n ≥ 1,

(1)

where Sst (1) = 1 and for n ≥ 2, Sst (n) = Sst (n − 1), n, Sst (n − 1).
Based on the above definition we have, for example, the transition sequence of the 4-bit standard Gray code as S(4) = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 4. The standard Gray code, also
known as the reflected Gray code, is the most celebrated topic. This code was a patented invention
due to Frank Gray in 1953, and was used to reduce the coding errors in a pulse code communication
system [6]. The wide spread utility of standard Gray codes is undisputed [2]. For particular applications, however, additional properties of Gray codes are sometimes desired. For examples, when
designing experiments, or when designing and testing electrical circuits and information systems,
balanced Gray codes are needed (cf. [3, 9]).
The transition sequence of a Gray code defines an (undirected) graph of transitions whose
vertex set [n], and whose edge set {{si , si+1 } : i ∈ {1, 2, ..., N − 1}}. Given a graph G with n
vertices. A G-code is a Hamiltonian path on the n-cube Qn whose graph of transition is a subgraph
of G. A cyclic G-code is a Hamiltonian cycle on Qn whose graph of transitions is a subgraph of G.
We can see that every G-code has a unique transition sequence of length N if G-code is cyclic, and
of length N − 1 otherwise. The graph ΓG(n) induced by a Gray code G(n) has vertex set [n] and
edge set {{si , si+1 } : i ∈ {1, 2, ..., N − 1}}. If G(n) is cyclic, the cyclic graph ΓG(n) induced by
G(n) is the graph ΓG(n) completed with the edge {sN −1 , sN } and {sN , s1 } which may be already
in ΓG(n) . We emphasize here that the graph ΓG(n) (or ΓG(n) ) is an undirected simple graph, i.e. if
a consecutive pair {si , si+1 } occurs more than once in S(n) (or S(n)), then we consider only one
edge joining si and si+1 in Γ(G(n) .
We should mention that if a G-code exists for a graph G, it does not mean that a Gray code
exists which induces the graph G. As an instance, for the cycle graph of three vertices C3 , there is a
C3 -code, but we can check by inspection that there is no Gray code which induces C3 . Furthermore,
we can immediately see that the complete bipartite graph K1,n or the star graph Stn with central
vertex 1 is induced by the standard Gray code of length n + 1. Motivated by the construction of
a particular type of Hamiltonian cycle in the cube-connected-cycle, CCCn , Bultena and Ruskey in
[4] observed the existence of G-codes for various type of Graphs G. The cube-connected-cycle is
a well known topology in computer networks (see [4]). The following result is due to Bultena and
Ruskey in [4].
313

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

Theorem 1.1. For any complete multipartite graph G, there is a cyclic G-code.
Besides introducing some graphs G which are G-codes, Wilmer and Ernst in [14] also introduced some graphs which are induced by Gray codes. They in [14] also proposed to put attention
to graphs of many edges: should not typical Gray codes induce many edges graphs? Based on this
suggestion, Suparta and van Zanten in [12] proved the existence of Gray codes inducing complete
graphs. In this paper we will show that some bipartite graphs are induced by Gray codes. Particularly we show that complete bipartite graphs are induced by Gray codes. Before closing this
section, we will introduce the following definitions to facilitate the next discussion.
We define S(n)k , 0 ≤ k ≤ N , as the following.
If the sequence S(n) = s1 , ..., sk , sk+1 , sk+2 , ..., sN , then S(n)k = sk+1 , sk+2 , ..., sN , s1 , ..., sk ,
with S(n)N = S(n)0 = S(n). In other words, we can say that S(n)k is obtained by shifting S(n)
in a cyclic sense over k positions to the left. For instance, consider the transition sequence S(4) =
2, 1, 2, 3, 4, 3, 2, 3, 4, 1, 4, 3, 2, 3, 4, 3 of a Gray code of length 4 which induces complete bipartite
graph K2,2 . This transition sequence has closing transition 3. Furthermore we have S(4)5 =
3, 2, 3, 4, 1, 4, 3, 2, 3, 4, 3, 2, 1, 2, 3, 4 which has closing transition 4.
Let u be a sequence of transition. The sequence obtained from u by reversing its order will be
denoted by uR . For example, if u is the sequence of transitions 1, 4, 3, 2, 3, of S(4), then uR is the
sequence 3, 2, 3, 4, 1.
2. A Construction for Gray codes
In many cases, properties of Gray codes may be studied using their transition sequences (see
e.g. [9, 11, 13]). In this article, we also use transition sequence of Gray code in studying some
property of transition graph which is induced by the Gray code like Suparta and van Zanten did in
[12].
The following lemma is due to Gilbert in [5] which describes some characteristics of transition
sequence of a path or a cycle.
Lemma 2.1.
1. A sequence T = a1 , a2 , ..., aL , ai ∈ {1, 2, ..., n} of length L is the transition sequence of a
path if and only if every non-empty consecutive subsequence of T contains at least one digit
an odd number of times.
2. A sequence T = a1 , a2 , ..., aL , ai ∈ {1, 2, ..., n} of length L is the transition sequence of
a cycle if and only if every non-empty consecutive subsequence of T of length less than L
contains at least one digit an odd number of times, while T itself contains every digit an even
number of times.
According to the Lemma 2.1, if the sequence S = s1 , s2 , ..., sN , with N = 2n , is a transition
sequence of a cyclic Gray code of length n, then we have that every consecutive subsequence of S
of length 1, 2, ..., or N −1 contains at least one digit an odd number of times, while in the sequence
S itself every digit occurs an even number of times.
The following theorem will leads us to construct the transition sequence of a Gray code of
length n based on the transition sequence of a Gray code of length n − 2 for n ≥ 2. A slight
314

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

different formulation of the theorem and its variation of proofs can be found in [1, 8, 10, 12]. Here
we will present a proof in a slightly different way as in [12]. We emphasize here that the number l
in the theorem is an odd integer.
Theorem 2.1. Let S(n − 2) := u0 , sj1 , u1 , sj2 , ..., ul1 , sjl , ul , s2n−2 be the transition sequence of an
(n − 2)-bit Gray code, and uk be a consecutive subsequence which may be the empty sequence.
The sequence S which equals
u0 , sj1 , u1 , sj2 , ..., ul1 , sjl , ul , n − 1
R
uR
l , n, ul , n − 1, ul , sjl ,
R
uR
l−1 , n − 1, ul−1 , n, ul−1 , sjl−1 ,
R
ul−2 , n, ul−2 , n − 1, uR
l−2 , sjl−2 ,
..
.

(row 1)
(row 2)
(row 3)
(row 4)

R
uR
1 , n, u1 , n − 1, u1 , sj1 ,
R
u0 , n − 1, u0 , n, uR
0 , n − 1,

(row l + 1)
(row l + 2)

is a transition sequence of an n-bit Gray code.
Proof. Let us consider the sequence S which is listed as l + 2 rows, and each row is a subsequence
of S, as is shown in the theorem. Let |u| be the length of the sequence u. We can see that the
length of the sequence in the first row is l + 1 + |u0 | + |u1 | + . . . + |ul | = 2n−2 , which is equal to
the length of the sequence S(n − 2). Moreover, the length of every subsequence of the next l + 1
rows is 3 + 3|uj | for some j ∈ {0, 1, 2, . . . , l}. Thus, the length of the whole sequence S is equal
to 4(l + 1 + |u0 | + |u1 | + . . . + |ul |) = 4 × 2n−2 = 2n . Furthermore, we can see easily that each
digit in S occurs an even number of times.
Now we need to show that any non-empty consecutive subsequence of S contains at least one digit
an odd number of times. To this end, let t be any non-empty proper consecutive subsequence of
S, and O(t) be the set of all integers in t which occur an odd number of times. We want to show
that O(t) is not the empty set for any condition for t. If t is a subsequence of S(n − 2), then it is
clear that O(t) is not the empty set, since S(n − 2) is a transition sequence (see Lemma 2.1). This
implies that for any consecutive subsequence uj of S(n − 2), if t is a non empty subsequence of
uj or of uR
j , then O(t) is also not the empty set.
Now suppose that t is not a subsequence of S(n−2), uj , nor of uR
j , for any consecutive subsequence
uj of S(n − 2). This means that n − 1 or n belongs to Z(t), the set of all integers in t. We have
two cases: i) n − 1 or n belongs to O(t), and ii) both n − 1 and n do not belong to O(t).
For case i), we are done, since this means that at least n − 1 or n occurs an odd number of times in
t.
Now assume that we are in case ii). This case suggests that the integers n − 1 and n occur an even
numbers of times in t. Based on the occurrences pattern of the integers n and n − 1 in the theorem,
the sequence t does not intersect the sequence of Row 1 in S. Thus, O(t) will be the same as O(u)
for some consecutive subsequence u of S(n − 2). Therefore, O(t) is not empty.
The sequence of transitions sj1 , sj2 , . . . , sjl in Theorem 2.1 plays an important role for some
characteristics of Gray codes defined by the resulting transition sequence S. In the sequel, the
315

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

sequence of transitions sj1 , sj2 , . . . , sjl as in Theorem 2.1, will be denoted using T . If there is no
confusion, we will omit commas when presenting transition sequences of Gray codes.
Remark 2.1. The position of digits n − 1 and n in Theorem 2.1 might be interchanged without
having to lose the role of the resulting sequence as a transition sequence of a Gray code. In general, interchanging digits i and j, 1 ≤ i, j ≤ n, will only interchange bit positions i and j in the
list of Gray code. The resulting Gray code will be said to be equivalent with the original Gray code.
Example 1
The complete bipartite graph K2,2 is induced by 4-bit Gray code having the transition sequence
S(4) = 212343234143234(3). Now we illustrate the use of Theorem 2.1 to construct the transition
sequence of a 6-bit Gray code. Set the sequence of transitions T := s3 , s6 , s7 , s10 , s15 = 2, 3, 2, 1, 4.
By applying Theorem 2.1 we can obtain the transition sequence S(6)
2123432341432345654323454323632341436345432563436345432125216125.
We immediately see that this transition sequence induces the complete bipartite graph K3,3 which
has diagram as in Figure 1.

Figure 1. Diagram of K3,3 induced by Gray code having transition sequence S(6).

Whenever we interchange all positions of digits 5 and 6 in the last transition sequence, we will
obtain 6-bit Gray code which is equivalent to the original one.
3. A procedure for constructing Gray codes inducing bipartite graphs
For some finite set X, as we defined for finite sequences, the number of elements in X will be
denoted by |X|. Let G(V, E) be a bipartite graph, and X and Y be the partition sets of the vertex
set V . If the graph G(V, E) is connected, |X| = m and |Y | = n, for some positive integers m and
n, then this connected bipartite graph will be denoted by Bm,n . The complete bipartite graph Km,n
is an instance of Bm,n .
Assume that some Gray code G(m+n−2) with transition sequence S(m+n−2) induces some
bipartite graph Bm−1,n−1 . Note that consecutive transitions in the transition sequence S(m+n−2)
will occur alternately as the elements of the set X and of the set Y . In other words, si ∈ X if and
only if si+1 ∈ Y , 1 ≤ i ≤ 2m+n−2 − 1. The following procedure of construction will result in a
transition sequence S of a Gray code inducing a bipartite graph of length m + n.
316

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

Construction
Let m and n be positive integers, with m, n ≥ 2. Consider the transition sequence S(m+n−2)
of a Gray code of length (m + n − 2) which induces bipartite graph Bm−1,n−1 . Then, continue with
the following steps.
1. If necessary, shift cyclically the transition sequence S(m + n − 2) such that its closing
transition is an element of X. Thus, S(m + n − 2) := S(m + n − 2), s2m+n−2 with s2m+n−2 ∈
X.
2. Set the sequence of transitions T := sj1 , sj2 , sj3 , . . . , sj2k−2 , s2m+n−2 −1 of length less than or
equal to the size of Bm−1,n−1 , i.e. the number of edges of Bm−1,n−1 , such that
{sj2 , sj4 , . . . , sj2k−2 } ⊂ X and {sj1 , sj3 , . . . , sj2k−3 , s2m+n−2 −1 } ⊂ Y .
Here, the length of sequence T is equal to 2k − 1 for some positive integer k.
3. Apply Theorem 2.1 to construct the transition sequence S := S(m + n).
Assume that S(n − 2) induces a bipartite Graph in Theorem 2.1. Observe the consecutive
subsequence sji , ui , sji+1 of S(n − 2), with sjl+1 := s2n−2 , for some 1 ≤ i ≤ l. Since sji ∈ X if
and only if sji+1 ∈ Y in the Contruction, we conclude that the number of components in ui is even.
First, assume that ui is not the empty sequence. Let v and w be the first and the last component of
ui . It is clear that v ∈ X if and only if w ∈ Y . Therefore, after applying step 3 of the Construction,
we have that v and m + n − 1 as well as w and m + n are consecutive in the resulting sequence
S(m + n). If ui is empty, then sji+1 and m + n − 1 as well as sji+1 and m + n will be consecutive
in the sequence S(m + n).
In the Construction, the consecutiveness of transitions in sequence T is not restricted. In practice, the sequence T might be chosen as a consecutive subsequence of S(m + n − 2).
In Example 1, if T is chosen as the consecutive subsequence 4143234 of 2123432341432343,
then we obtain the following transition sequence
S(6) = 2123432341432345654563652563654561654323432125212343236323432125.
Let Bm−1,n−1 be a connected bipartite graph with partition sets of vertices X and Y . Bm,n is
called derived from Bm−1,n−1 if the edges {m + n − 1, m + n}, {m + n, x}, and {m + n − 1, y}
are in graph Bm,n , for some pair of adjacent vertices x and y in graph Bm−1,n−1 . We also say that
Bm−1,n−1 derives Bm,n or Bm,n is a derivation of Bm−1,n−1 .
We can see that the Construction can be applied to derive some graph Bm,n from some related
graph Bm−1,n−1 , as shown in the following theorem.
Theorem 3.1. If there exists an (m + n − 2)-bit Gray code which induces a bipartite graph
Bm−1,n−1 , then there exists an (m + n)-bit Gray code which induces some bipartite graph Bm,n , a
derivation of the graph Bm−1,n−1 .
Proof. First, we should emphasize that the sequence T in the Construction is always possible to
be obtained. This is because each transition number si ∈ [m + n − 2] occurs at least twice in
S(m + n − 2). Therefore, after discarding a closing transition from S(m + n − 2), each transition
number will remains at least one in S(m + n − 2). Take the sequnce T which contains 2k − 1
317

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

transition numbers sj1 , sj2 , sj3 , . . . , sj2k−2 , s2m+n−2 −1 satisfying condition 2) in the Construction.
According to Theorem 2.1 we conclude that the resulting sequence S := S(m + n) is the transition
sequence of some (m + n)-bit Gray code. Since the transition s2m+n−2 −1 is in T , it implies that
transitions m + n − 1 and m + n occur consecutively in S(m + n). This means that the edge
{m + n, m + n − 1} is indeed in the graph induced by S(m + n). Futhermore, again based
on Theorem 2.1, we can see that transition x which occurs consecutively with some sjk ∈ X in
S(m + n − 2), will occur consecutively with m + n − 1 in S(m + n). Similarly, the transition
y which occurs consecutively with some sjl ∈ Y in S(m + n − 2), will occur consecutively with
m + n in S(m + n). This implies that edges {x, m + n − 1} and {y, m + n} are in the graph
induced by S(m + n).
4. Some bipartite graphs which are induced by Gray codes
In this section we will discuss some classes of bipartite graphs which are induced by some
Gray codes using the Construction. One of the classes is complete bipartite graphs class.
A corollary of Theorem 3.1 is the following.
Corollary 4.1. If there exists a Gray code of length m+n−2 which induces the complete bipartite
graph Km−1,n−1 , then there exists a Gray code of length m+n which induces the complete bipartite
graph Km,n .
Proof. By setting T = sj1 , sj2 , sj3 , . . . , sj2k−2 , s2m+n−2 −1 , as a consecutive subsequence of S(m +
n − 2) such that {sj2 , sj4 , . . . , sj2k−2 } = X and {sj1 , sj3 , . . . , sj2k−3 , s2m+n−2 −1 } = Y , then the
resulting transition sequence S(m + n) will induce the complete bipartite graph Km,n .
Example 2
The Gray code with transition sequence S(3) = 12321232 with closing transition 2 (in the
parentheses), induces the complete bipartite graph K1,2 . Choose T = 123 (boldface transitions in
S(3)). By applying Construction we get the sequence
S(5) = 12321234543452541232141232523214
which defines a 5-bit Gray code inducing the complete bipartite graph K2,3 .
Let m and n be any positive integers, with n > m. Assume that we want to construct a Gray
code of length m + n which induces the complete bipartite graph Km,n . It is well known that
the standard Gray code of length n − m + 2 induces the complete bipartite graph K1,n−m+1 . By
applying the Construction m − 1 times recursively to the previously resulting sequences, we will
obtain a Gray code of length m + n inducing the complete bipartite graph Km,n .
How about the complete bipartite graph Kn,n , n ≥ 1? For n = 1 is clear, since S st (2) induces
K1,1 . We can check by inspection that the transition sequence S(4) = 1234323414323432 defines
a 4-bit Gray code inducing the complete bipartite graph K2,2 . Now let us start from the S(4). By
applying the Construction n − 2 times recursively to the resulting sequences which are resulted
in from S(4), we will get a transition sequence S(2n) which induces the complete bipartite graph
Kn,n . So, for n ≥ 2 we can conclude that Kn,n is induced by some 2n-bit Gray code. Thus, based
on this observation we then have the following main result.
318

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

Theorem 4.1. For any pair of positive integers m and n, there exists a Gray code of length m + n
which induces the complete bipartite graph Km,n .
Proof. Using Example 2, Corollary 4.1, and all explanation just right before the theorem, then we
are done.
Now, we want to continue our observation to a class of bipartite graphs which has diagram
shown in Figure 2.

(1)

Figure 2. Diagram of graph Bn+k,1+k

Assume that the integers n ≥ 2 and k ≥ 1. This bipartite graph has n + 2k + 1 vertices. One
partition set has 1 + k vertices, and the other one has n + k vertices. Moreover, the graph has one
vertex of degrees n + k, one vertex of degrees k + 1, n − 1 vertices of degree 1, and 2k vertices
(1)
of degrees 2. Let us name this graph as bipartite graph of type 1, and denote by Bn+k,1+k . The
(1)

diagram in Figure 3 is an example of a bipartite graph of type 1, B3,2 , having 5 vertices.

(1)

Figure 3. Diagram of graph B3,2
(1)

This graph B3,2 is induced by the Gray code having the transition sequence
S(5) = 12131214541213121412131252131214.
Furthermore, by setting the sequence T = s31 = 1 (the boldface digit in S(5)), and then applying
Construction, we will get the following transition sequence
S(7) = 1213121454121312141213125213121676121312521312141213121454121312
1612131214541213121412131252131272131252131214121312145412131216
(1)

which induces the bipartite graph B4,3 the graph of which is shown in Figure 4.
319

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

(1)

Figure 4. Diagram of graph B4,3

In the next discussion we will show that for any integers n ≥ 2 and k ≥ 1, there exists a Gray
(1)
code which induces the bipartite graph Bn+k,1+k . To this end, we recall about the standard Gray
codes which was discussed at glance above. It is mentioned, just right before Theorem 1.1, that
the star graph of n + 1 vertices, Stn , is induced by the n + 1-bit standard Gray code. According to
the definition of the transition sequence of the n-bit standard Gray code as in Eq. (1), we have for
example the transition sequence S st (4) := 1213121412131214 for the 4-bit standard Gray code.
This transition sequence induces the star graph of 4 vertices, with vertex of label 1 as the center of
the star.
Consider the (n + 1)-bit standard Gray code, n ≥ 2, which induces the star graph of order n + 1
with the transition sequence S st (n + 1). The technique we do for constructing S(n + 3) which
(1)
induces Bn+1,2 is by taking the sequence T consisting of only one term s2n+1 −1 = 1 in S st (n + 1).
Using this sequence T for the Construction, we will obtain the transition sequence
S(n + 3) := Sst (n + 1), n + 2, n + 3, n + 2, Sst (n + 1)R , n + 2, S ∗ (n + 1), n + 3, S ∗ (n + 1)R , n + 2,
where S ∗ (n + 1) is the sequence obtained from Sst (n + 1) after lifting out the last transition.
According to Eq. 1, the first and the last transitions of Sst (n + 1) and of Sst (n + 1)R are 1. From
here we conclude that 1 and n + 2 are consecutive in S(n + 3). While the last transition of the
sequence S ∗ (n + 1) is the same as the first transition of S ∗ (n + 1)R which is the transition 2.
This implies that the transition 2 and n + 3 are consecutive in S(n + 3). Moreover we can see
immediately that the transitions n + 2 and n + 3 are consecutive in S(n + 3). Thus, we can finally
(1)
conclude that the transition sequence S(n + 3) induces the bipartite graph Bn+1,2 . By recursively
applying this technique we have proven the following theorem.
Theorem 4.2. For every integers n ≥ 2 and k ≥ 1, a Gray code of length n + 2k + 1 exists which
(1)
induces the bipartite graph Bn+k,1+k .
Below we will discuss another class of connected bipartite graphs induced by Gray codes. This
class consists of graphs of 2k vertices, k ≥ 2, where each partition set of vertices has k vertices.
Further characteristics of the graphs are that they have 2 vertices of degrees k, and 2k − 2 vertices
(2)
of degrees 2. The diagram of this class of graphs is shown in Figure 5, and will be denoted by Bk,k .
Example 3
We can verify that the sequence S(4) = 1232123432123214 is the transition sequence of Gray
(2)
code which induces the graph B2,2 . Here, all vertices have degrees 2. To obtain a Gray code of
320

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

(2)

Figure 5. Diagram of graph Bk,k
(2)

length 6 which induces B3,3 , again we apply the same technique, that is by setting T := s24 − 1 =
s15 = 1 (the bold face in S(4)) for the Construction. By interchanging the digits 5 and 6 when
applying Theorem 2.1, then we have the transition sequence
S(6) := 1232123432123216561232123432123216123212343212325232123432123216,
(2)

(2)

which induces the bipartite graph B3,3 . In this graph B3,3 , two vertices (vertices 1 and 2) are of
degrees 3, and 4 vertices (vertices 3, 4, 5, and 6) are of degrees 2. By observing carefully how
the Construction works, we can easily see that the degrees of vertices 1 and 2 each will increase
(2)
by 1 each time we construct the next derivation graph. Thus, the characteristics of being Bk,k are
maintained.
Remark 4.1. The interchange of digits 5 and 6 in the transition sequence is only for maintaining
the adjacency of odd-even labels in the related graph. This does not influence the structure of the
graph.
Based on the above observation, we have the following theorem.
Theorem 4.3. For every positive integer k ≥ 2 there exists a Gray code of length 2k which induces
(2)
the bipartite graph Bk,k .
(2)

Proof. Example 3 shows that a Gray code of length 4 exists which induces B2,2 . Note that in
that S(4) we have the subsequences s1 , s2 = 1, 2 and s24 −2 , s24 −1 = s14 , s15 = 2, 1. Preceding
the theorem, we described some technique how we obtain a Gray code of length 6 inducing the
(2)
bipartite graph B3,3 . Using the technique we get the transition sequence S(6) of the 6-bit Gray code
which maintains the propertiy that the subsequences s1 , s2 = 1, 2 and s26 −2 , s26 −1 = s62 , s63 =
2, 1. This condition results in the degrees of vertices 1 and 2 to increase by 1, and keep the degrees
of other vertices when we construct the next derivation graph using the Construction. Thus, in
(2)
B3,3 , deg(1) = deg(2) = 3 and four other vertices are of degrees 2.
Assume that the transition sequence S(2k) of length 2k, k ≥ 2, exists which defines a Gray code
(2)
inducing Bk,k , and has the characteristics that the subsequences s1 , s2 = 1, 2, s22k −2 , s22k −1 = 2, 1,
deg(1) = deg(2) = k, and 2k − 2 other vertices are of degrees 2. For constructing a Gray code of
(2)
length 2k + 2 = 2(k + 1) inducing Bk+1,k+1 , we can accomplish by taking T := s22k −1 = 1.
Then, by applying the Construction, we will obtain a transition sequence S(2k + 2) which induces
(2)
(2)
Bk+1,k+1 . Based on Theorem 2.1, we can conclude that in Bk+1,k+1 , deg(1) = deg(2) = k + 1.
According to mathematical induction principle, we have proven the theorem.
321

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

(3)

Figure 6. Diagram of graph Bk,k

The last class of bipartite graphs which is induced by Gray code has diagram as in Figure 6.
This bipartite graph class has 2k vertices, for some positive integer k ≥ 3, and has characteristics as follows: the graph has k + 1 vertices of degrees 2, 2 vertices of degrees 3, and k − 3 vertices
(3)
of degrees 4. This type of graphs will be denoted by Bk,k .
Example 4
The transition sequence
S(6) := 3212321412321235653212321412321235321232141232126212321412321235
(3)

defines a 6-bit Gray code which induces B3,3 and has the following diagram.

(3)

Figure 7. Diagram of graph Bk,k

This graph has the characteristics described above: k + 1 = 4 vertices of degrees 2, 2 vertices
of degrees 3, and k − 3 = 0 vertex of degree 4.
Note that the subsequence s22k−2 −1 , s22k−2 , s22k−2 +1 , s22k−2 +2 = s15 , s16 , s17 , s18 = 3, 5, 6, 5
in S(6). This notion is important in studying the resulting transition sequence in terms of the
(3)
(3)
characteristics of B4,4 . To construct a Gray code inducing B4,4 based on the Construction, we do
the following. Shift cyclically 24 + 1 = 17 positions to the left so that the transition s22k−2 +1 =
s17 = 6 becomes the closing transition. Then, after shifting we have a transition sequence
S(6) := 5321232141232123532123214123212621232141232123532123214123212356.
By choosing the sequence T = s22k −1 = s63 = 5 (bold face transition) and then applying the
Construction we will have some new adjacent transitions {5, 7}, {7, 8}, and {3, 8}. Therefore,

322

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

deg(5) and deg(3) each increases by 1, and deg(7) = deg(8) = 2. The complete transition sequence
is as follows.
S(8) = 5321232141232123532123214123212621232141232123532123214123212357
8753212321412321235321232141232126212321412321235321232141232123
5753212321412321235321232141232126212321412321235321232141232123
8321232141232123532123214123212621232141232123532123214123212357.
(3)

This transition sequence defines an 8-bit Gray code which induces B4,4 . Furthermore, we can
see from S(8) that deg(1) = deg(7) = deg(4) = deg(6) = deg(8) = 2, deg(2) = deg(5) = 3, and deg(3)
= 4. We notice again that the subsequence s22k−2 −1 , s22k−2 , s22k−2 +1 , s22k−2 +2 = s63 , s64 , s65 , s66 =
5, 7, 8, 7 in S(8).
Considering this last works we formulate the following result.
Theorem 4.4. For every k ≥ 3 there exists a Gray code of length 2k which induces the bipartite
(3)
graph Bk,k .
Proof. The proof of theorem will be accomplished using mathematical induction principle. Let us
start from Example 4 which explains that a 6-bit Gray code and an 8-bit Gray code exist inducing
(3)
(3)
B3,3 and B4,4 respectively. Assume that for k ≥ 4 there exists a 2k-bit Gray code which induces
(3)
Bk,k , and its transition sequence is obtained by the Construction such that the graph has k + 1
vertices (vertices 1, 2k − 1, 4, 6, . . . , 2k − 2, and 2k), of degrees 2; k − 3 vertices (vertices 3, 5, . . . ,
and 2k − 5), of degrees 4; and 2 vertices (vertices 2 and 2k − 3,) of degrees 3. Moreover, based
on the notions given in Example 4, in general we can conclude that the transition sequence S(2k)
has subsequence s22k−2 −1 , s22k−2 , s22k−2 +1 , s22k−2 +2 = 2k − 3, 2k − 1, 2k, 2k − 1. By shifting
the transition sequence S(2k) over 22k−2 + 1 positions to the left, and applying the Construction
with the sequence T = s22k −1 in the new transition sequence, we will get the transition sequence
S(2k + 2) of a (2k + 2)-bit Gray code. In this transition sequence we obtain 3 new adjacent
(3)
transitions: {2k − 3, 2k − 1}, {2k − 1, 2k}, {2k − 5, 2k}. Thus, in the bipartite graph Bk+1,k+1
we will have (k + 1) + 1 = k + 2 vertices (vertices 1, 2k − 1, 4, 6, . . . , and 2(k + 1)) of degrees 2;
(k + 1) − 3 = k − 2 vertices (vertices 3, 5, . . . , and 2k − 3) of degrees 4; and 2 vertices (vertices
2 and 2k − 1) of degrees 3.
Acknowledgement
The author would like to express his gratitude to anonymous reviewers for their invaluable
inputs.
References
[1] A. Ádám, Truth function and the problem of their realization by two terminal graphs, in
Akadémiai Kiadó, (1968) Budapest.
[2] E. Agrell, J. Lassing, E.G. Strom and T. Ottosson, On the optimality of the binary reflected
Gray codes, IEEE Trans. Inform. Theory 50 (2004), 3170–3182.
323

www.ejgta.org

Some classes of bipartite graphs induced by Gray codes

|

I Nengah Suparta

[3] G.S. Bhat and C.D. Savage, Balanced Gray codes, Electron. J. Combin. 3 (1996), #R25.
[4] B. Bultena and F. Ruskey, Transition restricted Gray codes, Electron. J. Combin. 3 (1996),
#R11.
[5] E.N. Gilbert, Gray codes and paths on the n-cube, Bell System. Tech. J. 37 (1958), 815–826.
[6] F. Gray, Pulse code communications, U.S. Patent 2632058, 1953.
[7] C.E. Killian and C.D. Savage, Antipodal Gray codes, Discrete Math. 281 (2004), 221–236.
[8] D.E. Knuth, The Art of Computer Programming, Sorting and Searching (2005), 2nd Edition,
Addison-Wesley, USA.
[9] J.P. Robinson and M. Cohn, Counting sequences, IEEE Trans. Computers 39 (1997), 605–
629.
[10] I N. Suparta, A simple proof for the existence of exponentially balanced Gray codes, Electron.
J. Combin. 12 (2005), #N19.
[11] I N. Suparta and A.J. van Zanten, Balanced maximum counting sequences, IEEE Trans.
Inform. Theory 52 (2006), 3827–3830.
[12] I N. Suparta and A.J. van Zanten, A construction of Gray codes inducing complete graphs,
Discrete Math. 308 (2008), 4124–4132.
[13] D.J. Wagner and J. West, Construction of uniform Gray codes, Congressus Numerantium 80
(1991), 217–223.
[14] E.L. Wilmer and M.D. Ernst, Graphs induced by Gray codes, Discrete Math. 257 (2002),
585–598.

324

www.ejgta.org