IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 52 (2014), 1196
ISSN 2232-2094
ON ISOMORPHISM CLASSES OF GENERALIZED FIBONACCI CUBES
Jernej Azarija Sandi Klavzar Jaehun Lee Jay Pantone Yoomi Rho
Ljubljana, March 6, 2014
On Isomorphism Classes of Generalized Fibonacci Cubes
Jernej Azarija1, Sandi Klavzar1,2,3, Jaehun Lee4, Jay Pantone5, and Yoomi Rho4
Jh
1Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia
jernej.azarija@gmailcom
vO
2Faculty of Mathematics and Physics, University of Ljubljana, Slovenia 3Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
sandiMavzar@fmf.uni-lj.si
4Department of Mathematics, Incheon National University, Korea dlwogen257@naver.com, rho@incheon.ac.kr
_
5Department of Mathematics, University of Florida, USA jaypantone@ufl.edu
CM
The generalized Fibonacci cube Qd(f) is the subgraph of the d-cube Qd CO	induced on the set of all strings of length d that do not contain f as
a substring. It is proved that if Qd(f) = Qd(f') then |f | = |f'|. The 2	key tool to prove this result is a result of Guibas and Odlyzko about
the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings f,f' such that Qd(f) = Qd(f'),
CD U
CO
CO	or binary complementation. Strings f and f' with |f | = |f = d — 1 for
which Qd(f) = Qd(f') are characterized
where |f | > |(d + 1) and f' cannot be obtained from f by its reversal
1. Introduction
i-h
An element of (0,1}d is called a binary string (henceforth just called a string) of length d, with the usual concatenation notation. For example, 0d-11 is the string of length d consisting of d — 1 0 bits CD	followed by a single 1 bit. We will denote by e® = 0® 110d ® the ith unit string in (0,1}d.
Let d > 1 be a fixed integer. The d-cube Qd is the graph whose vertices are the binary strings of length d, with an edge connecting vertices v1 and v2 if the underlying strings differ in exactly one position. Given a graph G, the set of vertices of G is denoted by V(G). We use dG(u, v) to denote the length of the shortest path connecting u and v in G. Lastly, we will write G = H to signify that the graphs G and H are isomorphic.
Jh
Date: March 4, 2014
Key words and phrases. Fibonacci cube; generalized Fibonacci cube; graph isomorphism; combinatorics on words; autocorrelation polynomial
AMS 2010 Subject Classification. 05C60, 68R15
A
o
For a given string f and integer d, the generalized Fibonacci cube Qd(f) is the subgraph of Qd induced by the set of all strings of length d that do not contain f as a consecutive substring. Indeed, this generalizes the notion of the d-dimensional Fibonacci cube rd = Qd(11), which is the graph obtained from the d-cube Qd by removing all vertices that contain the substring 11.
Fibonacci cubes were introduced by Hsu [2] as a model for interconnection networks. Like the vO	hypercube graphs, Fibonacci cubes have several properties which make them ideal as a network
topology, yet their size grows significantly slower than that of the hypercubes. Fibonacci cubes have been extensively investigated; see, for example, the recent survey by Klavzar [6] and even more recent papers of Klavzar and Mollard [7] and Vesel [14]. In the first of these papers, different asymptotic properties of Fibonacci cubes are established, while in the latter a linear recognition algorithm is designed for recognizing Fibonacci cubes, improving the previous best recognition algorithm of Taranenko and Vesel [12].
Later, Ilic, Klavzar, and Rho [3] introduced the idea of generalized Fibonacci cubes (as defined above). Under the same name, the graphs Qd(1s) were studied by Liu, Hsu, and Chung [9] and Zagaglia Salvi [13]. The analysis of the properties of generalized Fibonacci cubes led to the study of several problems related to the combinatorics of words. To study their isometric embeddability into hypercubes, good and bad words were introduced by Klavzar and Shpectorov [8], where it was proved that about eight percent of all words are good. Isometric embeddability and hamiltonicity of generalized Fibonacci cubes motivated the ideas of the index and parity of a binary word, as defined by Ilic, Klavzar, and Rho [4, 5].
In this paper we consider the following fundamental question about the generalized Fibonacci cubes: for which binary strings f and f' and positive integers d are the generalized Fibonacci cubes Qd(f) and Qd(f') isomorphic? It is easy to see that if f' is the binary complement of f, or if f' is the reverse of f (the reverse of f = fi ... fd is fd ... fi), then Qd(f) = Qd(f') for any dimension d. Hence we say that a pair of binary strings f, f' is trivial if f' can be obtained from f by binary
CM
complementation, reversal, or composition of these mappings. We are therefore only interested in 00	the behavior of the other pairs, which we call the non-trivial pairs.
CM
We proceed as follows. In the next section, we prove that if Qd(f) = Qd(f'), then |f| = |f'|. We also prove that there exist non-trivial pairs of strings f,f' such that Qd(f) = Qd(f'), where |f | > 2(d + 1). In the last section, we prove that if |f | = d — 1, then Qd(f) = Qd(f') if and only if f and f' have the same block structure. Several conjectures are posed along the way.
CO
HH
2. The Length of Forbidden Words
In this section we first prove that if Qd(f) = Qd(f'), then |f | = |f'|. Then we pose the question whether there is some relation between |f | (= |f'|) and d provided that Qd(f) = Qd(f'). To this end we prove that there exist non-trivial pairs f, f such that Qd(f) = Qd(f') and |f | > |(d +1). We also conjecture that for any non-trivial pair f, f' such that Qd(f) = Qd(f'), we must have |f | > |(d + 1).
The autocorrelation polynomial pf (z) associated to a binary string f = fi ... fk g {0,1}k is defined
CD
as
k-i E<
Pf(z) = > cz"
where ci = 1 if the length k — i suffix of f is equal to the length k — i prefix of f, i.e., if fi+i... fk = fi ... fk-i, and ci = 0 otherwise; see Flajolet and Sedgewick [10, p. 60]. Note that the autocorrelation polynomial of f g {0,1}k is of degree at most k — 1 and has degree k — 1 if and only if the last bit of f is equal to the first bit of f. Observe also that
k-i
Pok (z) = J2 zi and p0k-ii(z) = 1.	(1)
We note in passing that more generally, pf (z) = 1 + z + ••• + zk-1 if and only if f = 0k or f = 1k and that pf (z) = 1 if and only if every non-trivial suffix of f is different from the prefix of f of the same length. Such words were named prime in [5].
CM	The following theorem establishes that only strings which have the same length can generate iso-
morphic generalized Fibonacci cubes.
vO
o u
Theorem 2.1. If |f |, \f'\ < d and Qd(f) = Qd(f), then |f| = \f'\.
Proof. Set nd(f) = |V(Qd(f))| and assume that |f | < |f'|. We will show that nd(f) < nd(f'), from which the theorem follows.
The key idea of the proof is to apply a result of Guibas and Odlyzko [1, p. 204] stating that if g and g' are binary strings such that pg(2) > pg<(2), then nd(g) > nd(g'). Moreover, since the values nd(g) only depends on pg(z), cf. [10, Proposition 1.4], we also infer that if |g| = |g'| and pg(2) = pgr(2), then nd(g) > nd(g'). It follows that if f is a binary string of length k < d, then
nd(0k-11) < nd(f) < nd(0k) .	(2)
In addition, since 0k is a strict substring of 0k 1 we infer that
o
nd(0k) <nd(0k 1) .	(3)
Combining (2) and (3) we conclude that
nd(f) < nd(0k) <nd(0k 1) < nd(f'),
CM
where the last inequality is due to the assumption that |f'| > k.	□
Hence, non-trivial pairs f,f' such that Qd(f) = Qd(f') are of the same length. We next ask what is the relation of this length with the dimension of the corresponding generalized Fibonacci cubes. The following result could be the extremal case.
Theorem 2.2. If k > 2, then Qd(0k 1k) = Qd(0k+11k-1) for any d < 3k - 1.
£
Proof. Let k > 2 be a fixed integer and set f = 0k 1k, f' = 0k+11k-1, G = Q3k-1(f), and G' = Qsk-1(f'). Let X = V(Qsk-1) \ V(G) and X' = V(Qsk-1) \ V(G'). For any 0 < i < k let
HH
Xi = {ufv : |u| = i, |v| = k - 1 - i} .
Then, by definition,
k1
X = y Xi.
i=0
Let w = w1 ...w3k-1 be an arbitrary vertex whose underlying string is in Xi. It then follows that wk+1... w2k-1 = 0i1k-i-1, and so Xj n Xk = 0 holds for all j = k. Since |Xi| = 2k-1, we have |X| = k2k-1. With a parallel argument we infer that also |X'| = k2k-1. This implies that |V (G)| = |V (G')|.
Consider now the mapping a : V(Q3k-1) ^ V(Q3k-1) defined by
a(u1 . .. U3k-1) = U1 ... UkU2kUk+1 .. . U2k-1U2k+1 . .. u3k-1 .
In particular, a fixes the first k and the last k — 1 coordinates. Since transposition of coordinates, complementation of a coordinate, and any composition of such mappings are all automorphisms of a hypercube, a is an automorphism of Q3k-1. Consider now G and G' as subgraphs of Q3k-1 and the restriction a|G of a to G. Since |V(G)| = |V(G')|, it remains to prove that a|G : V(G) ^ V(G').
Suppose on the contrary that for some u g V(G) we have a|G(u) = w G V(G'). Then w = x0k+1lk—1y, where |x| = i for some 0 < i < k, and |y| = k — i — 1. It is straightforward to see that o]G1(w) = x0klky. Since this is not a vertex of V(G) we have a contradiction.
CM	We have thus proved the result for d = 3k — 1. Note that all of the above arguments also work for
2k + d< 3k — 2 and when d < 2k, the assertion is trivial.	□
vO o

Gï
u CU
Motivated by the last theorem we pose:
Conjecture 2.3. If f and f are binary strings such that Qd(f) = Qd(f'), then Qd—i(f) =
Qd—i(f '
Conjecture 2.4. Let f, f be a non-trivial pair such that Qd(f) = Qd(f'). Then |f | > 2(d + 1).
We have verified these conjectures for small strings using the Sage package [11]. More precisely, we tested both conjectures for all d < 12 and all non-trivial pairs f,f'. See Appendix A for the corresponding procedures.
3. The Number of Blocks in Forbidden Words
O
In this section we characterize the binary strings f, f' of length d — 1 for which Qd(f ) = Qd(f '). It turns out that they are precisely the strings with the same block structure.
Let v(f) denote one less than the number of blocks of f = fif2 ... f|f |. For example v(0110) = 2. When a bit is different from the previous bit we call its index an index of bit change and denote it by ij. Therefore fi6— = fj for ix < i2 < ■■■ < i„ff).
Theorem 3.1. Let d > 2 and let f, f' be binary strings of length d — 1. Then v(f) = v(f') if and only if Qd(f ) = Qd(f').
CO
Proof. Set A = V (Qd) \ V (Qd (f ))_^hen A = {ff, ff, f ff |, f ff }. Similarly set A' = V (Qd) \ V (Qd(f')) = {fi f',.fi f'J'ff'f}. Let 2 < i! < ■■■ < iv{f) < d — 1 be the indices of bit change of f and let 2 < i\ < ■ ■ ■ < i'vf,) < d — 1 be the indices of bit change of f'. Since
(ff )t = (ff )t = fr-i for 2 < T < d — 1 and (fff |)T = (fffi)T = fT for 2 < r < d — 1, the strings fif and ff|f| are different precisely for r = ij, 1 < j < v(f). It follows that dqd(ff,ff\f |) = v(f) and by a parallel argument dqd (fi f', fff ,|) = v(f').
Assume first that v(f) = v(f'). We may without loss of generality assume that fi = f[ = 0. Then f|fI = f\f|. Let $ be a permutation of {1,...,d} such that ij) = ij, $(1) = 1, $(d) = d. Set ^(xi... xd) = yi ...yd, where
= \ x4,-1(t)! if f4,-l{T) = fT,
I ~xI-T7~)', otherwise.
CO
As transposition of coordinates, complementation of a coordinate, and compositions of such mappings are automorphisms of a hypercube, ^ is an automorphism of Qd. Also ^ sends the vertices of A to A'. Thus ^ is an isomorphism from Qd(f) to Qd(f').
CO
To prove the converse assume that Qd(f) = Qd(f'). We may without loss of generality assume that
v(f) < v(ff').
Assume v(f) = 0. Then ff = ff\f\ and hence |A| = 3, while |A'| =4 if v(f') = 0. Therefore v(f') = 0.
CD	Assume v(f) = 1. Then note that the vertices from A induce a path on four vertices and hence
|E(Qd(f ))| = d2d-i — (4d — 3). If v(f') > 1, then the vertices from A' induce two disjoint copies of K2 and hence E^ff')^ = d2d-i — (4d — 2) = E^ff ))|. We conclude that v (f) = 1.
For the rest of the proof we can thus assume that v (f ) > 2. The subgraph of Qd induced on A consists of two edges {Tiffif} and^ {ff|/|,ff^} where dffffifi) = v (f ) and dfiffWl ) = v (f ) + 2. Denote fif, fif, ffj |, ffj | by a, b, c, d, respectively. Consider the shortest b, c-path constructed by changing from left to right the bits in which b and c differ:
b = f if ^ fif + eh ^ fif + e-h + eî2 ^----> f if + +-----h eiv(f) = f fj| = c,
where addition is taken modulo 2.
Denote the j-th internal vertex f if + ei1 + ■■■ + eij of this path by Xj for 1 < j < v (f ) — 1. Similarly, denote Jj', ff', f'ff, f'j by a', V, c', d', respectively. Set k = v(f) — 1, i = v(f') — 1, and recall that k > 1. Let ^ : Qd(f ) ^ Qd(f ') be an isomorphism and let xj = Xj) for 1 < j < k.
Assume k = 1. Then xi is of degree d — 2 and hence deggd j,)(x' i) = d — 2. This means that x'i is adjacent to two vertices among a', b', c!, dd. As Qd is bipartite, x{ is adjacent to one of a', b' and one of c!, dd. If x{ is adjacent to b' and c', then i + 1 = dçd (b', c') < 2 and hence i = 1. If x{ is adjacent to a' and c', then i + 2 = dçd (a!, c') < 2, a contradiction. Similarly we get contradictions if x[ is adjacent to dd.
Assume k > 2. Then the vertices xi and xk of Qd(f ) are of degree d — 1. Considering that xi ^ ■ ■ ■ ^ xk is a path in Qd(f), we see that dqdjf)(xi,xk) = k — 1. Therefore the vertices x{ and x'k of Qd(f') are of degree d — 1 and dQd(fi)(x'i,x'k) = k — 1. We distinguish three cases.
Case 1: (xi and x k are adjacent to a common vertex among a', b', c!, d')
Now, k — 1 = dQd (xi, xJk) < 2 and hence k < 3. Also, k is odd as Qd is bipartite, and thus k = 3. Considering that xix2x3 is a shortest path in Qd, it follows that xi and x3 have distance two and hence have a common neighbor which is different from x2 in Qd. Call it u. Then, u is not a, b, c, or d because of its distances from xi and x3. Therefore u G Qd(f ). Set u' = u). Then u' G Qd(f ') and hence dQd (xi ,u') < dQd(f ')(x'i ,u') = dQd(f ) (x i,u) = 1, which means that dQd (xi ,u') = 1. CO	Similarly, dQd(x'3,u') = 1. Hence in Qd, x{ and x3 have three common neighbors: u', x'2, and one
CM	of a', b', c!, d'. This is a contradiction, because hypercubes are K2 3-free.
CM
From now on we regard that x[ and x'k are not adjacent to a common vertex among a' ,V ,c! ,dd. Case 2: (x1 and x k are either adjacent to a' and b' or adjacent to cC and d')
We may without loss of generality assume the first. Then k — 1 = dQd (x1, x'k) < 3 and hence k < 4. Also, k is even as Qd is bipartite. Therefore k = 2 or k = 4. We distinguish two subcases.
Case 2a: (k = 2)
It is well-known that in Qd a given edge lies in d — 1 cycles of length 4. Among the 4-cycles containing the edge x1x2, one contains b and another contains c. This means that there are d — 3 cycles of length 4 containing the edge x1x2 in Qd(f). Among the 4-cycles containing the edge x1x2, only one contains a' and b' together, and no other contains a',b',c', or d'. This means that there are d — 2 cycles of length 4 containing the edge x'1x'2 in Qd(f'), a contradiction.
CD
Case 2b: (k = 4)
It is known that for two given vertices at distance three, there are exactly three internally vertex-disjoint shortest paths in Qd, and therefore there are such paths between x1 and x4. Let R = x1uvx4 be any one of them which is different from x1x2x3x4. Considering the distances of u,v from x1,xk, we obtain that u,v e Qd(f) and hence R is a path in Qd(f). Therefore ^(R) is a path in Qd(f). By the assumption that k = 4, there is also an x\, x4-path through a' and bb, implying that there are (at least) four internally disjoint shortest paths between x\ and x'4 in Qd, which is a contradiction.
CD
Case 3: (x1 is adjacent to one of a' and b' while x'k is adjacent to one of c' and d', or vice versa)
Firstly, assume that x\ is adjacent to b while xk is adjacent to c. Then
o Ö
CO CD
€ + 1 = dQd (b',c')
O
<	dqd (b',xi) + dQd (x1 ,xk) + dQd (xk,c')
= 2 + dQ d (xi ,xk )
<	2 + dQd(f ')(x'i,x'k) = 2 + dQd(f )(xi,xk) = k + 1 .
$H
Hence, under this assumption i = k.
Alternatively, assume that xi is adjacent to a' while x'k is adjacent to C. Then,
i + 2 = dQd (a',c')
<	dQd (a',x'l)+ dQd (xi,xk ) + dQd (xk,C)
<	2 + dQd(f' )(xi,xk)
= k + 1 ,
a contradiction. The other cases similarly lead to contradictions.	□
This conjecture has also been verified for all dimensions up to 12 (and all non-trivial pairs f,f'); see Appendix A for the Sage code.
If 1/1 = l/'l < d — 2, then v(f) = v(f') in general no longer implies that Qd(f) — Qd(f'). For instance, it can be checked that Q6(0110) — Q6(0100) despite the fact that v(0110) = v(0100). On the other hand we pose the following conjecture.
Conjecture 3.2. Let /, /' be a non-trivial pair such that Qd(f) — Qd(f). Then v (/) = v(f').
CM CM
Acknowledgments: This research was supported by the bilateral Korean-Slovenian project BI-KR/13-14-005 and the International Research & Development Program of the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (MSIP) of Korea(Grant number: NRF-2013K1A3A1A15003503). J.A. and S.K. are supported by the Ministry of Science of Slovenia under the grant P1-0297. J.L. and Y.R. are supported by the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology grant 2011-00253195.
J.P.'s research was sponsored by the National Science Foundation under Grant Number DMS-1301692. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.
References
Jh
[1]	L.J. Guibas, A.M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981) 183-208.
I '
[2]	W.-J. Hsu, Fibonacci cubes—a new interconnection topology, IEEE Trans. Parallel Distrib. Syst. 4 (1993) 3-12.
Jh
[3]	A. Ilic, S. Klavzar, Y. Rho, Generalized Fibonacci cubes, Discrete Math. 312 (2012) 2-11.
[4]	A. Ilic, S. Klavzar, Y. Rho, The index of a binary word, Theoret. Comput. Sci. 452 (2012) 100-106.
[5] A. Ilic, S. Klavzar, Y. Rho, Parity index of binary words and powers of prime words, Electron. J. Combin. 19 (2012) #P44.

o
CM
i
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
u
a
CD U
[6] S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim. 25 (2013) 505-522.
[7]	S. Klavzar, M. Mollard, Asymptotic properties of Fibonacci cubes and Lucas cubes, to appear in Ann. Comb.
[8]	S. Klavzar, S. Shpectorov, Asymptotic number of isometric generalized Fibonacci cubes, European J. Combin. 33 (2012) 220-226.
J-i
[9]	J. Liu, W.-J. Hsu, M. J. Chung, Generalized Fibonacci cubes are mostly Hamiltonian, J. Graph Theory 18 (1994) 817-829.
[10] R. Sedgewick, P. Flajolet, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
[11] W. A. Stein et al., Sage Mathematics Software (Version 6.0.0), The Sage Development Team, 2013, http://www.sagemath.org.
112, A. I—o, A. Ve«l, ^ rec°gMti°n of ^onacc cu^, A,go„t.hmica 49 (2OO7) M-93.
[13] N. Zagaglia Salvi, On the existence of cycles of every even length on generalized Fibonacci cubes, Matematiche (Catania) 51 (1996) 241-251.
[14] A. Vesel, Linear recognition and embedding of Fibonacci cubes, to appear in Algorithmica. DOI 10.1007/s00453-013-9839-3.
A. Sage Programs Supporting the Stated Conjectures
In order to test our conjectures we define the function isom_classes that returns a dictionary whose entries are nontrivial pairs.
vO
0
o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
u
a
CD U
def	genFib(d,f):	
	G = graphs.CubeGraph(d)	
	V = [v for v in G.vertices() if	v. find(f) ! = -1]
	G.delete_vertices(V)	
	return G	
def	inv(f):	
	return ''.join(['1' if e ==	else for e in f])
def	nu(s) :	
	cur = s[0]	
	ret = 0	
	for i in range(1,len(s)):	
	if s[i] != cur:	
	ret+=1	
	cur = s[i]	
	return ret	
def	allStr(k):	
	ret = set()	
	for f in CartesianProduct(*[['®'	,'1']]*k):
	f = ''.join(f)	
	if inv(f) not in ret and f[:	:—1] not in ret and
	inv(f[::-1]) not in ret and	inv(f)[:: —1] not in ret:
	ret.add(f)	
	return ret	
def	isom_classes(d):	
	D = {}	
	for k in range(3,d):	
	for f in allStr(k):	
	G = genFib(d,f)	
	s = G.canonical_label().	graph6_string()
	if s not in D:	
	D[s] = [f]	
	else :	
	D[s]+=[f]	
	return D	
Conjecture 2.3 was tested with the following method.
def testConj1(d):
D = isom_classes(d) CM	for key in D:
for f1,f2 in Combinations(D[key],2) G1 = genFib(d-1,f1) G2 = genFib(d-1,f2) if not G1.is_isomorphic(G2): return False
A
o u
return True
vO
u
a
CD U
sage : all(testConj1 (i) for i in xrange(2 , 12)) True
Conjecture 2.4 was tested with the following method.
Finally, Conjecture 3.2 was tested with the following method.
def testConj2(d):
D = isom_classes(d) for key in D:
if len(D[key]) > 1 and len(D[key][0]) < (2/3)*(d+1) return False return True
o
sage : all([testConj2(i) for i in xrange(3,12)]) True
CM -
CM
def testConj 3(d) :
D = isom_classes(d) for key in D:
if len(set([nu(f) for f in D[key]])) > 1: return False return True
sage : all([testConj3(i) for i in xrange(3,12)]) True
m
CD
$H
CD
m