A306967 a(n) is the first Zagreb index of the Fibonacci cube Gamma(n).

2, 6, 22, 54, 132, 292, 626, 1290, 2594, 5102, 9864, 18792, 35362, 65838, 121454, 222246, 403788, 728972, 1308562, 2336946, 4154170, 7353310, 12965904, 22781520, 39897410, 69662166, 121292998, 210642966, 364928532, 630794356

Offset

1,1

Comments

The Fibonacci cube Gamma(n) can be defined as the graph whose vertices are the binary strings of length n without two consecutive 1's and in which two vertices are adjacent when their Hamming distance is exactly 1.

The first Zagreb index of a simple connected graph is the sum of the squared degrees of its vertices. Alternatively, it is the sum of the degree sums d(i)+d(j) over all edges ij of the graph.

In the Maple program, T(n,k) gives the number of vertices of degree k in the Fibonacci cube Gamma(n) (see A245825).

Links

Table of n, a(n) for n=1..30.

S. Klavžar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522.

S. Klavžar, M. Mollard and M. Petkovšek, The degree sequence of Fibonacci and Lucas cubes, Discrete Mathematics, Vol. 311, No. 14 (2011), 1310-1322.

Formula

a(n) = Sum_{k=1..n} T(n,k)*k^2, where T(n,k) = Sum_{i=0..k} binomial(n-2*i, k-i) * binomial(i+1, n-k-i+1).

Conjectures from Colin Barker, Mar 28 2019: (Start)

G.f.: 2*x*(1 + 2*x^2 - x^3) / (1 - x - x^2)^3.

a(n) = 3*a(n-1) - 5*a(n-3) + 3*a(n-5) + a(n-6) for n>6.

(End)

Example

a(2) = 6 because the Fibonacci cube Gamma(2) is the path-tree P_3 having 2 vertices of degree 1 and 1 vertex of degree 2; consequently, the Zagreb index is 1^2 + 1^2 + 2^2 = 6 (or (1 + 2) + (2 + 1) = 6).

Maple

T:=(n, k) -> sum(binomial(n - 2*i, k - i) * binomial(i + 1, n - k - i + 1), i = 0..k): seq(add(T(n, k)*k^2, k=1..n), n=1..30);

Crossrefs

Cf. A245825.

Sequence in context: A147800 A246624 A212872 * A324913 A027561 A321626

Adjacent sequences: A306964 A306965 A306966 * A306968 A306969 A306970

Keyword

nonn

Author

Emeric Deutsch, Mar 26 2019

Status

approved