C. Dalfo´ a , M. A. Fiol^b

^aDepartament de Matematica, Universitat de Lleida, Igualada (Barcelona), Catalonia `

^bDepartament de Matematiques, Universitat Polit ` ecnica de Catalunya, `

Barcelona Graduate School of Mathematics, Institut de Matematiques de la UPC-BarcelonaTech (IMTech), ` Barcelona, Catalonia

cristina.dalfo@udl.cat, miguel.angel.fiol@upc.edu

The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k − 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and `, with ` ∈ {2k − 2, 2k − 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs.

Keywords: n-step Fibonacci number, Fibonacci graph, digraph on alphabet, de Bruijn digraph, line digraph, adjacency matrix, spectrum

Mathematics Subject Classification: 05C20, 05C50.

DOI: 10.5614/ejgta.2021.9.2.22

Received: 28 July 2020, Revised: 27 September 2021, Accepted: 3 October 2021.

The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.

1. Preliminaries

Let us first introduce some basic notation and results. A digraph G = (V, E) consists of a (finite) set V = V (G) of vertices and a set E = E(G) of arcs (directed edges) between vertices of G. As the initial and final vertices of an arc are not necessarily different, the digraphs may have loops (arcs from a vertex to itself), and multiple arcs, that is, there can be more than one arc from each vertex to any other. If a = (u, v) is an arc from u to v, then vertex u (and arc a) is adjacent to vertex v, and vertex v (and arc a) is adjacent from u. The converse digraph G is obtained from G by reversing the direction of each arc. Let G⁺(v) and G⁻(v) denote the set of arcs adjacent from and to vertex v, respectively. A digraph G is k-regular if |G⁺(v)| = |G⁻(v)| = k for all v ∈ V . A cycle is a closed walk in which all its vertices are different.

The adjacency matrix A of a digraph G = (V, E) is indexed by the vertices in V , and it has entries (A)uv = α if there are α arcs from u to v, with α ≥ 0. Notice that, as we allow loops, the diagonal entries of A can be different from zero.

In the line digraph LG of a digraph G, each vertex of LG represents an arc of G, that is, V (LG) = {uv : (u, v) ∈ E(G)}; and vertices uv and wz of L(G) are adjacent if and only if v = w, namely, when the arc (u, v) is adjacent to the arc (w, z) in G. The k-iterated line digraph L ^kG is recursively defined as L ⁰G = G and L ^kG = L ^k−¹LG for k ≥ 1. It can easily be seen that every vertex of L ^kG corresponds to a walk v0, v1, . . . , v^k of length k in G, where (vi−1, vi) ∈ E for i = 1, . . . , k. Then, if there is one arc between pairs of vertices and A is the adjacency matrix of G, the uv-entry of the power A^k , denoted by a (k) uv , corresponds to the number of k-walks from the vertex u to the vertex v in G. The order n^k of L ^kG turns out to be

\[n_k = \mathbb{1}\boldsymbol{A}^k \mathbb{1}^\top, \tag{1}\]

where 1 stands for the all-one vector. If there are multiple arcs between pairs of vertices, then the corresponding entry in the matrix is not 1, but the number of these arcs.

If G is a strongly connected d-regular digraph, different from a directed cycle, with diameter D, then its line digraph L ^kG is d-regular with n^k = d ^kn vertices and has (asymptotically optimal) diameter D + k. In fact, for a strongly connected general digraph, the first author [5] proved that the iterated line digraphs are always asymptotically dense. For more details, see Harary and Norman [8], Aigner [1], and Fiol, Yebra, and Alegre [7].

Given integers d ≥ 2 and k ≥ 1, the de Bruijn digraph B(d, k) is commonly defined as a digraph on alphabet in the following way. This digraph has vertices x1x² . . . x^k with xⁱ ∈ [0, d−1] for every i = 1, 2, . . . , k. Moreover, every vertex x1x² . . . x^k is adjacent to the vertices x² . . . xkxk+1, where xk+1 ∈ [0, d − 1].

For the concepts and results on digraphs not presented here, see, for instance, Bang-Jensen and Gutin [3], Chartrand and Lesniak [4] or Diestel [6].

1.1. Generalized Fibonacci numbers

A proposed generalization of the well-known Fibonacci numbers is the following. Given an integer d ≥ 2, the d-step Fibonacci numbers F (d) 1 , F(d) 2 , F(d) 3 , . . . are defined through the linear

Figure 1. The 2-Fibonacci digraphs F(2, k) for k = 1, 2, 3, 4 as subdigraphs of the de Bruijn digraphs.

recurrence relation

\[F_k^{(d)} = \sum_{i=1}^d F_{k-i}^{(d)},\tag{2}\]

initialized with F (d) ^k = 0 for k ≤ 0 and F (d) ¹ = F (d) ² = 1. Thus, the cases d = 2, 3, 4, . . . correspond to the so-called Fibonacci numbers Fk, tribonacci numbers, tetrabonacci numbers, etc., respectively. For more information, see, for example, Miles [9].

In particular, the Fibonacci numbers hold the recurrence F^k = Fk−¹ +Fk−2, which, as it is well known, is satisfied by the numbers of the form

\[f(k) = a\phi^k + b\psi^k = a\left(\frac{1+\sqrt{5}}{2}\right)^k + b\left(\frac{1-\sqrt{5}}{2}\right)^k,\] (3)

where a and b are constants, φ = 1+^√ 5 2 is the golden ratio, and ψ = −φ −1 . Recall also that, from F⁰ = 0 and F¹ = 1, we get a = −b = 1/ √ 5, giving the Binet's formula F^k = (1/ √ 5)(φ ^k − ψ k ).

2. d-Fibonacci digraphs on alphabets

Definition 2.1. For some given integers d ≥ 2 and k ≥ 1, the d-Fibonacci digraph F(d, k) has vertices x = x1x² . . . xk, where for i = 0, . . . , k −1, xi+1 ∈ [0, d−1] if xi−¹ = 0, and xi+1 = xⁱ + 1 (mod d) otherwise. Moreover, every vertex x1x² . . . x^k is adjacent to the vertices x² . . . xkxk+1, where xk+1 ∈ [0, d − 1] if x^k = 0, and xk+1 = x^k + 1 (mod d) otherwise.

For instance, the 2-Fibonacci digraphs F(2, k) with k ≤ 4 and 2, 3, 5, 8 vertices, are shown in Figure 1, whereas the 1-Fibonacci digraphs F(d, 1) on d vertices, with d ∈ [2, 5], are depicted in Figure 3.

Some simple properties of the d-Fibonacci digraphs, which are easy consequences of their definition, are the following.

Lemma 2.1. Let F(d, k) be the d-Fibonacci digraph, with vertices x = x1x² . . . xk, for xⁱ ∈ [0, d − 1].

• (i) The out-degree of x is deg(x) = d if x^k = 0, and deg(x) = 1 otherwise.
• (ii) The digraph F(d, k) is an induced subdigraph of the de Bruijn digraph B(d, k).
• (iii) The digraph F(d, k) contains F(d 0 , k) as an induced subdigraph, for every d ⁰ ≤ d.
• (iv) There is a homomorphism φ from F(d, k) to F(d, k⁰ ), for every k ⁰ ≤ k.
• (v) The automorphism group of F(d, k) is the trivial one. Moreover, the digraph F(2, k) is isomorphic to its converse.

Proof. (i) follows immediately from Definition 2.1. Similarly, (ii) is a direct consequence of the definitions of F(d, k) and B(d, k). Concerning (iii), notice that the vertices of F(d, k) corresponding to the sequences x1x² . . . x^k with xⁱ ∈ {0, d−1, . . . , d−d ⁰+1} induce a subdigraph isomorphic to F(d 0 , k). Alternatively, from the results of Section 4, note that T^{d 0} is clearly an induced subdigraph of T^d for every d ⁰ ≤ d and, hence, the same property is inherited by F(d 0 , k) = L ^kT^d 0 and F(d, k) = L ^kTd. To prove (iv), we only need to exhibit the homomorphism from F(d, k) to F(d, k⁰ ), which is the following map on the corresponding sets of vertices

\[\phi: V(F(d,k)) \rightarrow V(F(d,k'))\] \[\boldsymbol{x} = x_1 x_2 \dots x_k \rightarrow \phi(\boldsymbol{x}) = x_{k-k'+1} x_{k-k'+2} \dots x_k.\]

Indeed, observe that if x → y, then φ(x) → φ(y). To prove the first part of (v), we only need to realize that every automorphism of F(d, k) must send the unique cycles of lengths 1 and 2 (loop and digon, where a digon is a directed cycle on two vertices) to themselves. This means that vertex 00 . . . 0 must be fixed, and the vertex set {0101, . . . , 1010 . . .} must be an orbit. But the only way to preserve the adjacencies between these two vertices and 00 . . . 0 is to fix them, which implies that all the other vertices have to be also fixed, and the automorphism is the identity. Finally, the second statement of (v) is justified by the mapping x1x² . . . x^k 7→ x^k . . . x2x1, which is an isomorphism between F(2, k) and its converse F(2, k).

In contrast with F(2, k), the Fibonacci digraph F(d, k) with d > 2 is not isomorphic to its converse. By using the line digraph approach of Section 4 again, this is a simple consequence of the fact that, for d > 2, T^d 6∼= Td. However, the same approach allows us to show that most of the properties of F(d, k) related to d-Fibonacci numbers are shared by its converse F(d, k).

To illustrate case (ii), in Figure 1, each Fibonacci digraph F(2, k) with k ≤ 4 is shown with thick lines as a subdigraph of its corresponding de Bruijn digraph B(d, k). In particular, note that F(d, 1) has d vertices, which coincides with the order d ^k of the de Bruijn digraph B(d, k) when k = 1. In contrast, the number of vertices of F(d, k) is much smaller when k increases, as the following result shows.

Proposition 2.1. The numbers of vertices N(d, k) of the d-Fibonacci digraphs F(d, k) satisfy the same linear recurrence as the d-step Fibonacci numbers in (2)

\[N(d, k+1) = \sum_{i=k-d+1}^{k} N(d, i) \qquad (k \ge 1),\] (4)

but now initialized with N(d, i) = 1 for \(i = -(d-2), -(d-1), \dots, 0\), and N(d, 1) = d.

Proof. For \(j \in [0, d-1]\), let \(n_j^k\) be the number of vertices \(x_1 x_2 \dots x_k\) of F(d, k) such that \(x_k = j\). Thus, \(n_j^1 = 1\) for \(j \in [0, d-1]\), \(N(d, k) = \sum_{j=0}^{d-1} n_j^k\) and, from the conditions on the digits \(x_i\), we get

\[\begin{array}{rcl} n_0^{k+1} & = & n_0^k + n_{d-1}^k, \\ n_1^{k+1} & = & n_0^k, \\ n_2^{k+1} & = & n_0^k + n_1^k, \\ & \vdots & & \\ n_{d-1}^{k+1} & = & n_0^k + n_{d-2}^k, \end{array}\]

or, in matrix form,

\[\boldsymbol{n}^{k+1} = \left(n_0^{k+1}, n_1^{k+1}, n_2^{k+1}, \dots, n_{d-1}^{k+1}\right)\] \[= \left(n_0^k, n_1^k, n_2^k, \dots, n_{d-1}^k\right) \begin{pmatrix} 1 & 1 & 1 & 1 & \dots & 1\\ 0 & 0 & 1 & 0 & \dots & 0\\ 0 & 0 & 0 & 1 & \dots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & 0 & \dots & 1\\ 1 & 0 & 0 & 0 & \dots & 0 \end{pmatrix} := \boldsymbol{n}^k \boldsymbol{R}. \tag{5}\]

Then, applying recursively (5), \(n^{k+1} = n^1 R^k = \mathbb{1} R^k\). Now, it is readily checked that the characteristic polynomial of the above recurrence \(d \times d\) matrix R is \(\phi(x) = x^d - \sum_{i=0}^{d-1} x^i\). Indeed, since

\[\phi(x) = \det(\mathbf{R} - x\mathbf{I}) = \det\begin{pmatrix} x - 1 & -1 & -1 & -1 & \dots & -1 \\ 0 & x & -1 & 0 & \dots & 0 \\ 0 & 0 & x & -1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & -1 \\ -1 & 0 & 0 & 0 & \dots & x \end{pmatrix},\]

we can expand the determinant relative to the first line to get \(\phi(x)=(x-1)x^{d-1}-x^{d-2}-x^{d-3}-\cdots-1\) (notice that, in doing so, every \((d-1)\times(d-1)\) submatrix have only one transversal with nonzero product \((x-1)x^{d-1}\), \(-x^{d-2}\), \(x^{d-3}\), etc.) Then, from \(\mathbf{R}^{k-d}\phi(\mathbf{R})=\mathbf{O}\), where \(\mathbf{O}\) is the all-zero matrix, we get

\[\boldsymbol{R}^k = \sum_{i=k-d}^{k-1} \boldsymbol{R}^i \tag{6}\]

or, multiplying both terms by the vector \(n^1 = 1\),

\[\mathbb{1}\mathbf{R}^{k} = \mathbf{n}^{k+1} = \sum_{i=k-d}^{k-1} \mathbb{1}\mathbf{R}^{i} = \sum_{i=k-d}^{k-1} \mathbf{n}^{i+1} = \sum_{i=k-d+1}^{k} \mathbf{n}^{i}.\] (7)

Hence,

\[N(d, k+1) = \sum_{j=0}^{d-1} n_j^{k+1} = \sum_{j=0}^{d-1} \sum_{i=k-d+1}^k n_j^i = \sum_{i=k-d+1}^k \sum_{j=0}^{d-1} n_j^i = \sum_{i=k-d+1}^k N(d, i),\]

as claimed. Besides, to show that the recurrence can be initialized with the d values N(d,i)=1 for \(i=d-2,d-1,\ldots,0\) and N(d,1)=d, we need to show that N(d,2)=N(d,1)+d-1, \(N(d,3)=N(d,2)+N(d,1)+d-2,\ldots,N(d,d)=\sum_{i=1}^{d-1}N(d,i)+1\). With this aim, note first that \(N(d,k)=\sum_{j=0}^{d-1}n_j^k=\boldsymbol{n}^k\mathbb{1}^\top=\mathbb{1}\boldsymbol{R}^{k-1}\mathbb{1}^\top\) for \(k=1,\ldots,d\), so that we first compute the vectors \(\boldsymbol{u}^{k-1}=\boldsymbol{R}^{k-1}\mathbb{1}^\top\) for \(k=0,1,\ldots,k+1\) to get:

\[\begin{aligned} & \boldsymbol{u}^{0} = \mathbb{1}^{\top} = (1, 1, 1, \stackrel{(d)}{\dots}, 1, 1)^{\top}, \\ & \boldsymbol{u}^{1} = \boldsymbol{R} \mathbb{1}^{\top} = (d, 1, 1, \stackrel{(d-1)}{\dots}, 1, 1)^{\top}, \\ & \boldsymbol{u}^{2} = \boldsymbol{R}^{2} \mathbb{1}^{\top} = \boldsymbol{R}(\boldsymbol{u}^{1})^{\top} = (d + (d-1), 1, \stackrel{(d-2)}{\dots}, 1, d)^{\top}, \\ & \boldsymbol{u}^{3} = \boldsymbol{R}^{3} \mathbb{1}^{\top} = \boldsymbol{R}(\boldsymbol{u}^{2})^{\top} = (2d + (d-1) + (d-2), 1, \stackrel{(d-3)}{\dots}, 1, d, d + (d-1))^{\top}, \\ & \vdots \\ & \boldsymbol{u}^{d} = \boldsymbol{R}^{d} \mathbb{1}^{\top} = \boldsymbol{R}(\boldsymbol{u}^{d-1})^{\top} \\ & = (2^{d-2}d + 2^{d-3}(d-1) + \dots + 1, d, d + (d-1), \dots, 2^{d-3}d + 2^{d-4}(d-1) + \dots + 2)^{\top}. \end{aligned}\]

Notice that, for each \(k=1,\ldots,d\), the sum of all entries of \(\boldsymbol{u}^{k-1}\) equals the first entry \(u_0^k\) of \(\boldsymbol{u}^k\). Consequently, \(N(d,k)=\mathbb{1}(\boldsymbol{u}^{k-1})^\top=u_k^0\), so giving

\[N(d,2) = u_0^2 = d + (d-1) = N(d,1) + d - 1,\]
\[N(d,3) = u_0^3 = 2d + (d-1) + d - 2 = N(d,2) + N(d,1) + d - 2,\]
:

\[N(d,d) = u_0^d = 2^{d-2}d + 2^{d-3}(d-1) + \dots + 1 = \sum_{i=1}^{d-1} N(d,i) + 1,\]

as required.

Since N(d,i) has no meaning for \(i \leq 0\), an alternative way of stating Proposition 2.1, would be to distinguish two cases: For \(k \geq d\), N(d,k+1) is computed by using 4; and, for \(1 \leq k < d\), we have

\[N(d, k+1) = \sum_{i=1}^{k} N(d, i) + d - k.\]

Table 1. The vectors \(n^k\), for k = 1, ..., 8, with entries \(n_j^k\) being the numbers of vertices \(x_1 x_2 ... x_k\) of F(5, k) such that \(x_k = j \in [0, 4]\), and the total number of vertices N(5, k).

Notice that, from (7), we proved that not only the total number of vertices of F(d, k) but also those vertices whose sequences end with a given digit \(j \in [0, d-1]\) satisfy similar recurrence relations as those of d-step Fibonacci numbers in (2). More precisely,

• If \(k \geq d\), then \(n_j^{k+1} = \sum_{i=k-d+1}^k n_j^i\) for \(j = 0, \dots, d-1\).
• If k < d, then \(n_j^{k+1} = \sum_{i=1}^k n_j^i + \varepsilon_j\), where
  • If \(j \in [1, d-1]\), then \(\varepsilon_j = 1\) if \(k \le j-1\), and \(\varepsilon_j = 0\) otherwise,
  • If j=0, then then \(\varepsilon_j=1\) if \(k\leq d-1\), and \(\varepsilon_j=0\) otherwise.

Notice that j = 0 behaves as \(j = d (\equiv 0 \mod d)\).

For example, for d=5, Table 1 shows the vectors \(\boldsymbol{n}^k\), for \(k=1,\ldots,8\), with entries being such number of sequences. Then, we can observe the claimed recurrences by looking at each j-th column of the formed array. For instance, when k=7(>d), we get \(n_j^8=\sum_{i=3}^7 n_j^1\) (8-th row in this table); whereas, for k=2, we have \(n_j^3=n_j^1+n_j^2+\varepsilon_j\), where \(\varepsilon_1=\varepsilon_2=0\) and \(\varepsilon_3=\varepsilon_4=\varepsilon_0=1\) (3-rd row in this table).

3. Fibonacci digraphs

Although a similar (although more involved) study for general d can be done, we concentrate here in the case d=2, where we simply refer to Fibonacci digraphs F(k). The reason is that, from Proposition 2.1, the numbers N(k)=N(2,k) of vertices of the (2-)Fibonacci digraphs F(k)=F(2,k) are

\[N(1) = 2\], \(N(2) = 3\), \(N(3) = 5\), \(N(4) = 8\), \(N(5) = 13\), \(N(6) = 21\), ...

which corresponds to the standard Fibonacci sequence \(F_3, F_4, F_5, F_6, F_7, F_8, \ldots\), see again Figure 1. Indeed, it is known that the number of binary sequences of length k without consecutive 1's is the Fibonacci number \(F_{k+2}\). For example, among the 16 binary sequences of length k=4,

Figure 2. The first four Fibonacci graphs as subgraphs of the hypercubes.

there are F⁶ = 8 without consecutive 1's. Namely, 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010 are the vertices of F(2, 4) in Figure 1. Indeed, such binary sequences also correspond to the vertices of the (undirected) Fibonacci graphs that are induced subgraphs of the k-cubes. So, two vertices are adjacent when their labels differ exactly in one digit. In Figure 2, we can see the first four Fibonacci graphs. For more information, see Hsu, Page, and Liu [10].

Now, let us show a result on the lengths of the cycles in the Fibonacci digraphs. More precisely, we prove that F(k) is semi-pancyclic.

Proposition 3.1. For every k ≥ 2, let ` = 2k − 2 if k is odd and ` = 2k − 1 if k is even. Then, the Fibonacci digraph F(k) is (1, `)-pancyclic, that is, it contains a cycle of every length 1, 2, . . . , `.

Proof. A p(> 1)-periodic vertex of F(k) has 1's in the positions i(≤ k), i + p, i + 2p, . . . Then, by cyclically shifting at the left the corresponding sequence, but keeping the periodicity, such a vertex gives rise to a cycle of length p. For instance in F(7), the vertex 0001000 gives the 4-cycle

\[0001000 \rightarrow 0010001 \rightarrow 0100010 \rightarrow 1000100 \rightarrow 0001000.\]

The other cycles (of lengths k + 1, k + 2, . . . , `) go either through the vertex 0 = 00 . . . 0 or the vertex 1 = 00 . . . 01. In both cases, if we look at the successive sequences of the cycle as the rows of an array, the entries 1 form a number q = 1, 2, . . . , bk/2c of anti-diagonals, as shown in Table 2 for k = 7 and q = 1, 2, 3. We label the corresponding cycles with the prefixes [0, q] and [1, q], respectively. Then, summarizing, we have the following cases:

• The vertex 0 gives a cycle of length 1 (a loop).
• The p-periodic vertices give cycles of length p for p = 2, 3, . . . , k.
• The [1, q]-cycles, containing vertex 1, have length k + 2q − 2 for q = 1, 2, . . . , bk/2c. (For q = 1, the cycle of length k is also obtained in the previous case for p = k.)
• The [0, q]-cycles, containing vertex 0, have lengths k + 2q − 1 for q = 1, 2, . . . , bk/2c. In particular, for q = bk/2c, the [0, bk/2c]-cycle has length ` = k+2bk/2c−1 ∈ {2k−2, 2k− 1}, as required.

This completes the proof.

Table 2. Cycles of lengths 7-8, 9-10, and 11-12 in F(7).

4. d-Fibonacci digraphs as iterated line digraphs

The following result shows that the d-Fibonacci digraphs can also be constructed as iterated line digraphs. Let \(T_d\) be the digraph with set of vertices \(\mathbb{Z}_d\) and arcs (0,i) for every \(i \in \mathbb{Z}_d\), and arcs (i,i+1) for every \(i = \mathbb{Z}_d \setminus 0\). Thus, \(T_d\) has d vertices and 2d-1 arcs. Moreover, it is a strongly connected digraph with diameter D = d-1. As examples, see Figure 3.

The adjacency matrix A of \(T_d\), indexed by the vertices \(0, 1, \ldots, d-1\), has first row 1, the all-one vector, and i-th row the unit vector \(e_{i+1}\), for \(i=1,2,\ldots,d-1\) (recall that the arithmetic is modulo d). Then, A coincides with the recurrence matrix R in (5) and, hence, the entries of the powers of A satisfy the recurrence

\[(\mathbf{A}^{k+1})_{uv} = \sum_{i=k-d+1}^{k} (\mathbf{A}^{i})_{uv}\] (8)

for \(k \geq d\).

In the following result, we show that the d-Fibonacci digraphs can also be defined as iterated line digraphs of \(T_d\).

Proposition 4.1. The d-Fibonacci digraph F(d,k) coincides with the (k-1)-iterated line digraph of \(T_d\), that is \(F(d,k) = L^{k-1}T_d\), for \(k \ge 0\), with \(F(d,1) = L^0T_d = T_d\).

Proof. We know that the vertices of \(L^{k-1}T_d\) correspond to the walks of length k-1 in \(T_d\). But, according to Definition 2.1, such walks are in correspondence with the sequences of length k defining the vertices of F(d,k). Moreover, the adjacencies in \(L^{k-1}T_d\) are the same as in F(d,k).

As a consequence of the last proposition and the proof of Proposition 2.1, we have the following result.

Figure 3. The digraphs T^d = F(d, 1) for d = 2, 3, 4, 5.

Proposition 4.2. Let F(d, k) be the d-Fibonacci digraph with N = N(d, k) vertices given by Proposition 2.1. Let A(k) and A be, respectively, the adjacency matrices of F(d, k) and Td.

• (i) The diameter of the d-Fibonacci digraph F(d, k) is D = k + d − 2.
• (ii) The eigenvalues of F(d, k) are the d zeros of the polynomial p(x) = x ^d−x ^d−¹−x ^d−²−· · ·−1 (or, alternatively, the d zeros different from 1 of the polynomial q(x) = x ^d+1 − 2x ^d + 1) plus N − d zeros.
• (iii) Fo any given d, k ≥ 0, the total number of closed l-walks Cl(d, k) in F(d, k) satisfies the same linear recurrence as the d-step Fibonacci numbers in (2), initiated with Cl(d, k) = tr A^l for l = 0, . . . , d − 1.
• Proof. (i) Since the diameter of T^d is D = d − 1 , the result follows from Proposition 4.1 and the results in Fiol, Yebra, and Alegre [7].
  • (ii) Since A = R, the characteristic polynomial φ(x) of T^d is φd(x) = x ^d − P^d−^{1 r}=0 x r . Hence, from the results in Balbuena, Ferrero, Marcote, and Pelayo [2], the characteristic polynomial of F(d, k) = L ^kT^d is ψ(x) = x ^N−^dφ(x), which gives the result.
• (iii) From (ii), the nonzero eigenvalues of F(d, k) and T(d) coincide. Then, for k ≥ 1, the total numbers of closed walks of length l, with l ≥ 1, in F(d, k) and in T^d coincide because tr A(k) ^l = tr A^l . But A coincides with the recurrence matrix R in (5), so that, from (8) and l ≥ d,

\[C_{l+1}(d,k) = \operatorname{tr} \mathbf{A}^{l+1} = \sum_{i=l-d+1}^{l} \operatorname{tr} \mathbf{A}^{i} = \sum_{i=l-d+1}^{l} C_{i}(d,k),\] (9)

and \[C_l(d, k) = \text{tr } A^k \text{ for } l = 0, ..., d - 1.\]

For instance, in the case of Fibonacci digraphs (d = 2), (9) becomes the version of 3 for the number of closed walks in F(2, k). Namely,

\[C_l(2,k) = \phi^l + \psi^l = \left(\frac{1+\sqrt{5}}{2}\right)^l + \left(\frac{1-\sqrt{5}}{2}\right)^l,\] (10)

initiated with C0(2, k) = 2 and C1(2, k) = 1. Compare (10) with the Binet's formula F^l = (1/ √ 5)(φ ^l − ψ l ).

In fact, from (8) and the fact that every closed walk of length l in T^d gives a closed walk of the same length in F(d, k), and vice versa, we can prove that, for any given j, d ∈ [0, d − 1], the numbers C^j (d, k) of closed walks in the digraphs F(d, k) for k ≥ d follow the same recurrence of the d-step Fibonacci numbers. What is more, the same holds for the total number of walks in F(d, k), which go from the vertices of type x1x² . . . j to the vertices of type x1x² . . . j⁰ for any given j, j⁰ ∈ [0, d − 1]. In the case of d = 2, this is a consequence of the following known formula for the powers of the adjacency matrix of T2, as a particular case of (6),

\[\mathbf{A}^{k} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{k} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{k-1} + \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{k-2} = \begin{pmatrix} F_{k+1} & F_{k} \\ F_{k} & F_{k-1} \end{pmatrix}\]

for k ≥ 2.

The fact that (A^k )⁰⁰ = F^k corresponds to the number of closed walks of length k rooted at vertex 0 in the digraph T² is cited in the On-line Encyclopedia of Integer Sequences A000045 [11].

Acknowledgement

This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R.

References

• [1] M. Aigner, On the linegraph of a directed graph, Math. Z. 102 (1967) 56–61.
• [2] C. Balbuena, D. Ferrero, X. Marcote, and I. Pelayo, Algebraic properties of a digraph and its line digraph, J. Interconnect. Networks 4, no. 4, (2003) 377–393.
• [3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2nd. edition, 2009.
• [4] G. Chartrand and L. Lesniak, Graphs & Digraphs, Chapman and Hall, third ed., London, 1996.
• [5] C. Dalfo, Iterated line digraphs are asymptotically dense, ´ Linear Algebra Appl. 529 (2017) 391–396.
• [6] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, fourth ed., Springer-Verlag, Heilderberg, 2010.
• [7] M.A. Fiol, J.L.A. Yebra, and I. Alegre, Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Comput. C-33 (1984) 400–403.

• [8] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo 9, no. 4, (1960) 161–168.
• [9] E.P. Miles Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67, no. 8, (1960) 745–752.
• [10] W.-J. Hsu, C.V. Page, and J.-S. Liu, Fibonacci cubes: a class of self-similar graphs, Fib. Quart. 31 (1993) 65–72.
• [11] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, published on-line at http://oeis.org