IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1163 ISSN 2232-2094 WIENER INDEX AND HOSOYA POLYNOMIAL OF FIBONACCI AND LUCAS CUBES Sandi Klavzar Michel Mollard Ljubljana, September 27, 2011 WIENER INDEX AND HOSOYA POLYNOMIAL OF FIBONACCI AND LUCAS CUBES o fí Sandi KlavZar Faculty of Mathematics and Physics, University of Ljubljana, Slovenia e-mail: sandi.klavzar@fmf.uni-lj.si Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia CM Michel Mollard CM CNRS Université Joseph Fourier, Institut Fourier, BP 74, 100 rue des Maths, CM 38402 St Martin d'Hères Cedex;, France e-mail: michel.mollard@ujf-grenoble.fr CO (Received July 22, 2011) ^h Abstract In the language of mathematical chemistry, Fibonacci cubes can be defined as the resonance graphs of fibonacenes. Lucas cubes form a symmetrization of Fibonacci cubes and appear as resonance graphs of cyclic polyphenantrenes. In this paper it is proved that the Wiener index CD of Fibonacci cubes can be written as the sum of products of four Fibonacci numbers which in turn yields a closed formula for the Wiener index of Fibonacci cubes. Asymptotic behavior of the average distance of Fibonacci cubes is obtained. The generating function of the sequence of £ ordered Hosoya polynomials of Fibonacci cubes is also deduced. Along the way, parallel results $H ^ for Lucas cubes are given. CD 1 Introduction IN CM U CD CD a CD vD O In this paper we are interested in the Wiener index and more general distance properties of Fibonacci and Lucas cubes. Fibonacci cubes were introduced as interconnection networks [15] and later studied from many aspects, see the recent survey [17]. From our point of view it is important that Fibonacci cubes also play a role in mathematical chemistry: Fibonacci cubes are precisely the resonance graphs of fibonacenes which in turn form an important class of hexagonal CO chains [19]. (For related results about resonance graphs, known also as Z-transformation graphs, see [20, 23, 28, 29].) Moreover, Lucas cubes also found chemical applications in [30]. The Wiener index of a graph is the first and (one of) the most studied invariant(s) in mathematical chemistry, see for instance extensive surveys [9, 10] and recent papers [2, 3, 6, 8, 25, 26]. An equivalent approach to the Wiener index is to investigate the average distance of a graph, which is indeed frequently done in pure mathematics, cf. [7, 14]. From the recent papers on the Wiener index we point out that [8] contains many new results on the Wiener index of fibonacenes, the class of graphs that made Fibonacci cubes appealing in chemistry! Hence an investigation of the Wiener index and related invariants of Fibonacci cubes seems well justified. i We wish to add that results similar to ours were very recently obtained by Doslic in [11] 00 while studying conjugated circuits in benzenoid chains. In particular, Fibonacci numbers con- cm volved with themselves play a role here and there, and an average Kekule structure of an n-ring fibonacene contains approximately 2n^>(2^> + 1)/5 conjugated hexagons, where golden ration. The paper is organized as follows. In the next section concepts and results needed are given. Then, in Section 3, we prove that the Wiener index of Fibonacci cubes can be written as the sum of products of four Fibonacci numbers and use this result to deduce a closed formula for the Wiener index of Fibonacci cubes. Hence the Wiener index of Fibonacci cubes can be obtained in constant time which improves a result from [22] that computes it in O(log Fn) time. In addition, we also determine the asymptotic behavior of the average distance of Fibonacci cubes and obtain J-i parallel results for Lucas cubes. In Section 4 we consider the Hosoya polynomial and obtain the generating function of the sequence of ordered Hosoya polynomials of Fibonacci cubes as well (H as the corresponding generating function for Lucas cubes. To make the paper of a reasonable Jh length, we only indicate some of numerous possible uses of these generating functions. 2 Preliminaries IN CM U CD CD a CD vD O The distance in this paper is the usual shortest-path distance—the number of edges on a shortest path between vertices. The Wiener index W(G) of a connected graph G is the sum of distances over all unordered pairs of vertices of G. The vertex set of the d-cube Qd, also called a hypercube of dimension d, is the set of all binary strings of length d, and two vertices are adjacent if they differ in precisely one position. CO A Fibonacci string of length n is a binary string b]b2... bn with bibi+1 = 0 for 1 < i < n. The Fibonacci cube rn (n > 1) is the subgraph of Qn induced by the Fibonacci strings of length n. For convenience we also consider the empty string and set To = K1. Call a Fibonacci string b1b2.. .bn a Lucas string if b1 bn = 1. Then the Lucas cube An (n > 1) is the subgraph of Qn induced by the Lucas strings of length n. We also set A0 = K1. Let {Fn} be the Fibonacci numbers: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 for n > 2. Let Fn be the Fibonacci strings of length n. Let Fo0 and Fl the strings of Fn that end with, respectively, 0 and 1. A subgraph G of a graph H is an isometric subgraph if the distance between any vertices 1 of G equals the distance between the same vertices in H. Isometric subgraphs of hypercubes 00 2are partial cubes. The dimension of a partial cube G is the smallest integer d such that G is an CM isometric subgraph of Qd. Many (chemically) important classes of graphs are partial cubes, in particular trees, median graphs, benzenoid graphs, phenylenes, grid graphs and bipartite torus CO graphs. In addition, Fibonacci cubes and Lucas cubes are partial cubes are partial cubes as well, see [16]. Let a partial cube G of dimension k be given together with its isometric embedding into Qk. Then for i = 1, 2,..., k and x = 0,1, the semicube W(i)X) is defined as follows: m CD $H CD m W(i,x) (G) = {u = U1U2 ...uk e V (G) | m = x} . For a fixed i, the pair W(i 0)(G), W(i;1)(G) of semicubes is called a complementary pair of semicubes. It should be pointed out that since the embedding of G into Qk is unique (modulo permutation of coordinates), see [24], the definition of the semicubes does not depend on the £ embedding. The following result from [18] that computes the Wiener index of a partial cube Jh from the orders of their complementary pairs of semicubes will be our starting point in Section 3: Theorem 2.1 Let G be a partial cube of dimension k isometrically embedded into Qk■ Then k W (G) = £ |W(i)o)(G)|.|W(i,i)(G)|. i=i & The Hosoya polynomial [1, 27] (also known as the Wiener polynomial) H(G, x) of a connected graph G is the distance counting polynomial: H(G, x) = £ xd(u,v). {u,v} We refer to [4] for several polynomials related to the Hosoya polynomial: edge-Wiener poly- vO nomial, Schultz polynomial, and Gutman polynomial. It is often more convenient to consider i—l _ ordered Hosoya polynomial H(G, x), that is, the counting polynomial of the distances among ordered pairs of vertices: H(G, x) = £ xd(u'v). (u,v)GV (G) x V (G) For example, when using Cartesian product, ordered polynomials are more adapted because we have the simple relation H(G □ G',x) = H(G,x) ■ H(G',x). The two polynomials are easily CM linked as follows: CM 2H(G, x) = H(G, x) - |V(G)| = H(G,x) - H(G, 0). CM 3 Wiener index CO We begin by expressing the Wiener index of Fibonacci cubes with Fibonacci numbers: HH ^h Theorem 3.1 For any n > 0, w (r„) = > ]Fi Fi+1 Fn —i+1 Fn-i+2 • I-H i_1 Proof. The result holds for n = 0 because W(r0) = 0. Let n > 1 and recall that rn is a partial cube. Moreover, the dimension of rn is n, hence by Theorem 2.1 we have *Jh n W (rn) = jr |W(i,i)(rn)|-|W(i,0)(rn)| • 4J i=1 Consider the set W(i,1)(rn), where 2 < i < n — 1. Let b = b1 • • .bn G W(i;1)(rn), then bi = 1 which implies that bi—1 = 0 and bi+1 = 0. It follows that for 2 < i < n — 1, |W(i,1)(rn)| = |Fi—2| ■ |Fn—i—1|. Furthermore, |W(M)(rn)| = |W(n,1)(rn)| = |Fn—2|. n IN CM u CD a CD a CD CO CO vO 0 o CM 1 CM CO CM CM £ CO CO Similarly, |W(i)Q)(rra)| = |Fi_i| ■ |Fn_i| for 2 < i < n - 1 and |W(1;o)(r„)| = |W(ra,o)(rra)| |Fn-1|. Therefore, n— 1 W(rn) = Y, (|Fi-2| ■ |Fn-i-l| ■ |Fi-l| ■ |Fn-i|) + 2|Fn-2| ' |Fn-l| i=2 n = ^ F Fn-i+1 Fi+1 Fn-i+2 , i=1 where we have used that for any j, |Fj | = Fj+2. □ Note that the sequence {W(rra)}£=0 is the convolution of {FiFi+1}°=0 with {Fi+1Fi+2}°=0. In order to obtain a closed formula for W(rn) we will apply the appealing theory of Greene and Wilf presented in [12]. They studied the existence of closed formulas for expressions of the form n_1 Y G1(a1n + &1j + C1 )G2(a2n + b2j + C2) ■ ■ ■ Gfc(afcn + bfcj + cfc), j=o where each sequence {Gi(n)} is a sequence that satisfies a linear recurrence. Fibonacci numbers are of course such a sequence. Then it follows from [12, Theorem 2] that the sum S=~o Fi Fn_i+1 Fi+1 Fn_i+2 can be expressed as a linear combination of F^, Fn+1, FnFn+1, nF2, nF2+1, and nFraFra+1. Furthermore, [12, Theorem 3] implies that if a linear combination of the six monomials and the sum agree for n = 0,1,..., 5, then they agree for all n. Since the values of W(rra) = YH=1 F Fra_m Fm Fra_i+2 for n = 0,1,..., 5 are 0,0, 2,10,39,136, the values of the linear combination a F2 + b F?2+1 + c FnFra+1 + d nF2 + e nF2+1 + f nFraFra+1 must whose solution is CO CD $H CD CO u a CD U /0 1 0 0 0 0 a 0 1 1 1 1 1 1 b 0 1 4 2 2 8 4 c 2 4 9 6 12 27 18 d 10 9 25 15 36 100 60 e 39 25 64 40 125 320 200 V/z 136 (a, b, c, d, e ,/} = 4 23 4 6 9 ( 25 25'25'25'25} i+1 F+1 F n-i+2 = F 2 25 F n + A ^ 25 nF2 - 23 FF 25 FnF n+1 + 25 n Hence ^i=0 Fi Fn_i+1 Fi+1 Fn_i+2 = 25Fn + 25nFn — 25n+1 + 25nFnFn+1 + 25' therefore: Theorem 3.2 For any n > 0, W = 4(n + 1)Fra2 + (9n + 2)FraFra+1 + 6nFra2+1 25 25 25 CM CM The first values of the sequence {W(rn)} are 0,1,4,16, 54,176, 548, 2 Theorem 3.2 yields the asymptotic behavior of the average distance of Fibonacci cubes: IN For a (connected) graph G, its average distance ^(G) is defined as 1 MG) = W(G). rO | ' Corollary 3.3 lim ^n) =2 . n^TO n 5 Proof. From Binet's formula for the Fibonacci numbers it follows that Fn+1 1 + V5 lim —-— = ifi =-. n^TO Fn 2 1—1 Then Theorem 3.2 and the fact that |V(rn)| = Fn+2 imply: JH lim ^2 = 2 + ^ + =2 n^TO n \25^>4 25^3 25 1, W(An) = nF„_i Fn+i. CO CO Proof. We again use the fact that Lucas cubes are partial cubes [16] and hence Theorem 2.1 ~ can be applied, that is, W(An) = j |W(i;i)(An)|-|W(i;0)(An)| . i=1 Considering Lucas strings on a circle we infer that |W(i)i)| ■ |W(i 0)| does not depend of i. So we may assume that i = 1. There are |Fn-3| Lucas strings whose first coordinate is 1, and there are |Fn-1| Lucas strings whose first coordinate is 0. □ Using Binet's formula and Theorem 3.4 we obtain a result for the average distance of Lucas cubes parallel to Fibonacci cubes: Corollary 3.5 „„ ^(An) _ 2 CD Jh lim n >0 n,k>0 & where fn,k is the number of pairs of vertices (u, v) G V(rn) x V(rn) such that d(u, v) = k. CO Theorem 4.1 The generating function of the sequence of ordered Hosoya polynomials of rn is CO \ Tft^ \ n ! + z + xz(l - z) /(x, z) = £ H(rn, x)zn - -i-- o CD n>0 (ij 1 — z — z2 + xz(—1 — z + z2) Proof. For i, j G {0, l}, let fj be the number of (u, v) G V(rn) x V(rn) such that d(u, v) = k where u ends with i and v ends with j. Let us consider the generating polynomials fj(x,z) = En k>0 fr^kxkzn. Then, having in mind the empty string, C^ ' > ' /(x, z) = l + f00(x, z) + /01(x, z) + /10(x, z) + /n(x, z). (l) cm ^ By symmetry, CO /01(x,z) = / 10(x,z). (2) If u and v end with l then they are the concatenation of an arbitrary Fibonacci string of Fn-2 rn +V,no f11 CO we obtain by a standard computation that with 01 thus /nik = fn-2,k for n > 2. Using the initial conditions fO = 1 and fl = /¿0 = 0 / 11(x,z) = z2/(x,z)+ z. (3) If u and v end with 0 then they are both the concatenation of an arbitrary Fibonacci string of Fn-1 with 0 thus /n0k = fn-1 k for n > l. Using the initial condition /0 "0 = 0 we obtain ,00 /00(x,z) = zf(x,z). (4) For n > 2, if u ends with 1 and v ends with 0, then u is the concatenation of a Fibonacci CO string of with 1, and v is the concatenation of a string of F—iUF^! with 0. Therefore /n0k = /n_i,fc_i + /n_i,k_i. Using the initial conditions /1° = 1 and /1° = /¿,0, = 0 we obtain by summation that /1 0(x, z) — xz = xz/00(x, z) + xz/1 0(x, z) and thus f 10(x z) — (x'z) + xz — xz f(x,z) + xz (5) ' 1 — xz 1 — xz ' $H Using the symmetry (2), by substitution of the expressions (3), (4) and (5) in (1) we obtain the CO relation 2xz2 on - 2xz f (x,z)(1 - z ----z2) = 1 + z + 1 — xz 1 — xz thus the theorem. □ CO Theorem 4.1 can be applied in many different ways, let us mention some of them. By CO _ _ definition of H(G,x) we have that H(G, 0) — |V(G)|. Furthermore, it is well-know that H'(G, 1) — 2W(G), cf. [5, 13]. Theorem 4.1 gives that f (0, z) — 1_1z+fz2 and we can recognize the generating function of the sequence {Fj+2}°=0, the number of vertices of Furthermore, lx=i — (1-2z-2Zz2+z3)2. The generating function of the sequence {FFi+1}°=0, known as golden rectangle numbers being z/(1 — 2z — 2z2 + z3) [21, A001654]. We have thus an alternative proof that the sequence o {W(r„)}~=o is the convolution of {FFm}~0 with {F^F^}^. A remarkable property of f (x, z) is that partial derivations are easy to compute which leads CO us to the following: CM CM Corollary 4.2 Let k > 1. The generating function of the sequence {fnk }^=0 of number of pairs of vertices of rn at distance k is Z f n_ 2z(z + z2 - z3)k-1 n,kz = (1 - z - z2)k+1 n>0 Proof. By direct computation we have df (x,z) 2z dx (1 - z - z2 + xz(—1 - z + z2))2 d(1 - z - z2 + xz(—1 - z + z2)) _ ^ dX ax m (D and = z — z — z. Therefore it is easy to prove by induction that for any k > 1 dk f (x,z) 2(k!)z(z + z2 — z3)k-1 dxk (1 - z - z2 + xz(—1 - z + z2))k+1 We have thus dk f (x,z). 2(k!)z(z + z2 - z3)k-1 —rr k— |x=o — 9xk = (1— z - On the other hand, from f (x, z) — ^n k,>0 fn,k/xk zn we have for any fixed k, dk f (x,z) = v dxk ^ n>0 a > k!fn,fc + k! ^ fn,fc' x fc'>fc+1 fc'- fc The value for x — 0 implies the corollary. □ We continue with Lucas cubes: vO Theorem 4.3 The generating function of the sequence of ordered Hosoya polynomials for An ) — — )n = 1 + 2x2z3 - 3x2z4 + z2(1 + x)2 z) — H (An, x)z — , o 3 + x2z4 _ z2(1 + x)2 • fl ............. ... 1 — z — x2z3 + x2z4 — z2(1 + x)2 n> 0 To prove this result, let us first return to Fibonacci cubes. Let gnk be the number of O ' (u, v) G V(rn) x V(rn) such that d(u, v) — k where v begins with 0. For i, j G {0,1} let gj be i ' the number of (u, v) G V(rn) x V(rn) such that d(u, v) — k where u ends with i, v begins with ro 0 and ends with j. Let us consider the generating polynomials g(x,z) — ^nk>0 gn,kxkzn and CM g(x z) — En,fc>o gjfcxkzn. £ Lemma 4.4 The generating functions of gn k and g^k are 00 ' 1 ' g(x z) — 1 — z — z2 + xz(—1 — z + z2) — 1, 2 2 2 01 xz x z g01(x, z) — ---(g(x, z) + 1) + (1 — xz) 1 — x2z2 Proof. Assume throughout the proof that v begins with 0. In parallel to the general case we ^ have g(x, z) — g00(x, z) + g01(x, z) + g10(x, z) + g11(x, z) • (6) CD Assume n > 3. If u and v end with 1 then they are the concatenation of a string of Fn-2 with 01, arbitrary for u, beginning with 0 for v. Thus g11k — gn-2,k. Using the initial values G ' g^o — 1 g21,11 — g:1,1^ — g1,1) — g1>11 — g1,1) — g0,0 — 0 we obtain a g11(x,z) — z2g(x,z) + z2 • (7) zn Assume n > 2. If u and v end with 0 then they are both the concatenation of Fibonacci strings of Fn-1 with 0, arbitrary for u, beginning with 0 for v. Thus gn°k = gn-i,fc. Using the initial ^ values g°°° = 1, g°°i = g°°° = g°,° = 0 we get g°°(x,z)_ zg(x,z) + z. (8) CD Assume n > 2. If u ends with 1 and v ends with 0, then u is the concatenation of a Fibonacci CD string of Fj_i with 1, and v is the concatenation with 0 of a string of Fre—i^F^—i beginning with 0. Therefore gn°fc = ^n-1fc-1 + gn^ k-1. By a symmetrical argument we have g^fc = gn°-i,k-i + gn°-1,k-i. Therefore i—l oo gn°k + g 2g n-1,k-1 + g n-1,k-1 + g n-1,k-1 (n > 2) (9) and £ 10 01 10 01 gn,k - gn,k _ -(gn-1,fc-1 - gn-1,fc-1) (n > 2) . (10) The initial values being o g1° 1 g°1 _ g°1 _ g°1 _ g1° _ g1° _0 (11) g1,1 _ 1, g°,1 _ g1,° _ g°,° _ g1,1 _ g°,° _ 0. (11) cm Using these initial conditions and (9) we obtain by summation CM g1°(x, z) + g°1(x, z) — xz _ 2xz2g(x, z) + 2xz2 + xz(g1°(x, z) + g1°(x, z)) £ CO thus g1°(x, z) + g°1(x, z) _ (g(x, z) + 1) + . (12) 1 — xz 1 — xz By substitution in (6) of (7), (8) and (12) we obtain 2 2xz2 xz g(x, z) _ zg(x, z) + z2g(x, z) + —— (g(x, z) + 1) + —--+ z + z2 1 xz 1 xz £ thus the expression of g(x, z). From (10) and the initial values (11) we obtain that gnik—gn°k _ 0 for k _ n and gn1«,—gn°n _ -Jh ' ' ' ' e(—1)n when n > 1, therefore £ g°1 (x,z) — g1°(x,z)_I^. (13) • i From (13), (12) and g°1(x,z) _ -—(x'z)+g—(x'z)+2(g——we obtain the expression for £ g°1(x,z). □ Proof. (Theorem 4.3) Let ¿n,k be the number of (u, v) e V(An) x V(An) such that d(u, v) = k and like previously consider ¿j and the generating functions ¿(x,z) and ¿ij(x,z). We have again ¿(x, z) = 1 + ¿00(x, z) + ¿01(x, z) + ¿10(x, z) + ¿n(x, z). (14) g If u and v end with 0 then u and v are arbitrary vertices of F0 and thus ¿00(x,z) = f 00(x,z) = zf (x,z). (15) a CD CO 00 vO O c/3 CD Assume n > 2. If u and v end with 1 then they begin with 0 and thus u = 0u'01, v = 0v'01 where u' and v' are arbitrary strings of F0-2 or the empty string if n = 2. Furthermore ^k = 0 when n < 1. We have thus ¿n(x, z) = z2(f00(x, z) + 1) = z3f (x, z) + z2 . (16) Assume n > 2. If u ends with 0 and v ends with 1, then u is the concatenation with 0 of a string of F^UFU, and v is the concatenation with 1 of a string of F^ beginning with 0. Therefore =gn-1,k-1+gn-1,k-1=e.Notice that, when n ,e Z- transformation graphs, Discrete Math., 311 (2011), pp. 1681-1692. [21] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org, 2011. [22] K. R. Udaya Kumar Reddy, Computing Wiener index of Fibonacci cubes. manuscript, 2011. •in [23] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, CD MATCH Commun. Math. Comput. Chem., 53 (2005), pp. 195-208. [24] P. M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math., • 7 (1984), pp. 221-225. [25] B. Wu, Wiener index of line graphs, MATCH Commun. Math. Comput. Chem., 64 (2010), pp. 699-706. Jh [26] X. Wu AND H. Liu, On the Wiener index of graphs, Acta Appl. Math., 110 (2010), pp. 535-544. CD [27] S. Xu and H. Zhang, Hosoya polynomials of TUC4C8(S) nanotubes, J. Math. Chem., 45 ft (2009), pp. 488-502. CO [28] H. Zhang, P. C. B. Lam, and W. C. Shiu, Resonance graphs and a binary coding for the 1-factors of benzenoid systems, SIAM J. Discrete Math., 22 (2008), pp. 971-984. i—l [29] H. Zhang, L. Ou, and H. Yao, Fibonacci-like cubes as Z-transformation graphs, Discrete Math., 309 (2009), pp. 1284-1293. [30] P. Zigert and M. Berliz, Lucas cubes and resonance graphs of cyclic polyphenantrenes. manuscript, 2011. o CO CD Jh CD CO u a CD U