# Euler numbers and diametral paths in Fibonacci cubes, Lucas cubes and
Alternate Lucas cubes

Ömer Eğecioğlu Elif Saygı Zülfükar Saygı Department of Computer Science,
University of California Santa Barbara, Santa Barbara, California 93106, USA.
email<EMAIL_ADDRESS>of Mathematics and Science Education,
Hacettepe University, 06800, Ankara, Turkey. email:
<EMAIL_ADDRESS>of Mathematics, TOBB University of Economics
and Technology, 06560, Ankara, Turkey. email<EMAIL_ADDRESS>
###### Abstract

The diameter of a graph is the maximum distance between pairs of vertices in
the graph. A pair of vertices whose distance is equal to its diameter are
called diametrically opposite vertices. The collection of shortest paths
between diametrically opposite vertices are referred as diametral paths. In
this work, we enumerate the number of diametral paths for Fibonacci cubes,
Lucas cubes and Alternate Lucas cubes. We present bijective proofs that show
that these numbers are related to alternating permutations and are enumerated
by Euler numbers.
Keywords: Shortest path, diametral path, Fibonacci cube, Lucas cube, Alternate
Lucas cube, Euler number.
MSC[2020]: 05C38 05A05 11B68

##  1 Introduction

Given a connected graph $G=(V,E)$, one of the basic problem is to enumerate
the number of shortest paths between pairs of vertices in $G$. The solution to
this problem provides an important topological property of an interconnection
network, in terms of its connectivity, fault-tolerance, communication expense
[17] and has important applications such as for counting minimum $(s,t)$-cut
in planar graphs and route guidance systems [3].

The so-called single-source shortest paths problem consists of finding the
shortest paths between a given vertex and all other vertices in the graph. One
can solve this problem by using the algorithms such as Breadth-First-Search
for unweighted graphs or Dijkstra’s algorithm [8]. Similarly, Dijkstra’s
algorithm can be used to solve the single-pair shortest paths problem in a
weighted, directed graph with nonnegative weights.

The process of finding all shortest paths between a pair of vertices in a
graph is another problem. This can be considered a search for the most
efficient routes through the graph. In [4], it is proved that finding the
number of shortest paths in a general graph is NP-hard.

For planar graphs with $m$ vertices an oracle is presented in [2] to find the
number of shortest paths for a given pair of vertices whose time complexity is
$O(\sqrt{m})$ with $O(m^{1.5})$ space. This approach is improved in [11] and a
new oracle for counting shortest paths in planar graphs is presented, where
Voronoi diagrams are used to speed up the query time.

In the literature, the problem of enumerating the number of shortest paths
have been considered for some special families of graphs. Explicit formulas
have been obtained for the hexagonal network [10], the star graph [13], the
$(n,k)$-star graph [5, 7] and the arrangement graph [6]. In an $(n,k)$-star
graph the number of shortest paths is enumerated by counting the minimum
factorizations of a permutation in terms of the transpositions corresponding
to edges in that graph [7]. For the arrangement graph this number is
enumerated by establishing a bijection between these shortest paths and a
collection of ordered forests of certain bi-colored trees [6].

The distance $d(u,v)$ between two vertices $u,v\in V$ is the number of edges
in a shortest path between $u$ and $v$. The diameter of $G$ is defined as the
maximum distance between pairs of vertices in $V$ and is denoted by ${\rm
diam}(G)$.

A pair of vertices $u,v\in V$ with $d(u,v)={\rm diam}(G)$, are called
diametrically opposite vertices. The collection of shortest paths between
diametrically opposite vertices are referred to as diametral paths. For a pair
of diametrically opposite vertices $u,v\in V$ we let $c(u,v;G)$ denote the
number of diametral paths from $u$ to $v$ in $G$.

As an example, for the $n$-dimensional hypercube $Q_{n}$ the number of
diametral paths between any diametrically opposite pair $u$ and $v$ can be
enumerated by establishing a bijection between these shortest paths and the
permutations on $n$ symbols, so that

$c(u,v;Q_{n})=n!\,.$

In this paper we enumerate the number of diametral paths for three special
subgraphs of hypercube graphs, namely Fibonacci cubes [12], Lucas cubes [15]
and Alternate Lucas cubes [9]. We present bijective proofs of our results.
Surprisingly, these numbers are related to alternating permutations and are
enumerated by Euler numbers.

##  2 Preliminaries

We let $[n]=\\{1,2,\ldots,n\\}$. The $n$-dimensional hypercube $Q_{n}$ is the
graph defined on the vertex set $B_{n}$, where

$B_{n}=\\{b_{1}b_{2}\ldots b_{n}\mid b_{i}\in\\{0,1\\},\ i\in[n]\\}\,.$

Two vertices $u,v\in B_{n}$ are adjacent if and only if the Hamming distance
$d(u,v)=1$, that is, $u$ and $v$ differ in exactly one coordinate. For
convenience, $Q_{0}=K_{1}$. It is clear from the definition that ${\rm
diam}(Q_{n})=n$ and for any vertex $u\in B_{n}$ there exist a unique vertex
$\bar{u}\in B_{n}$ such that $d(u,\bar{u})=n$, where $\bar{u}$ denotes the
complement of the binary string of $u$.

For $n\geq 1$, let

${\cal FB}_{n}=\\{b_{1}b_{2}\ldots b_{n}\in B_{n}\mid b_{i}\cdot b_{i+1}=0,\
i\in[n-1]\\}\,.$

The $n$-dimensional Fibonacci cube $\Gamma_{n}$ ($n\geq 1$) is an induced
subgraph of $Q_{n}$ with vertex set ${\cal FB}_{n}$. We take
$\Gamma_{0}=K_{1}$. Similarly, for $n\geq 1$, let

${\cal LB}_{n}=\\{b_{1}b_{2}\ldots b_{n}\in{\cal FB}_{n}\mid b_{1}\cdot
b_{n}=0\\}$

and for $n\geq 3$,

${\cal ALB}_{n}=\\{b_{1}b_{2}\ldots b_{n}\in{\cal FB}_{n}\mid b_{n}\cdot
b_{n-2}=0\\}\,.$

The $n$-dimensional Lucas cube $\Lambda_{n}$ and Alternate Lucas cube ${\cal
L}_{n}$ are defined as the induced subgraphs of $\Gamma_{n}\subseteq Q_{n}$
and with sets ${\cal LB}_{n}$ and ${\cal ALB}_{n}$, respectively.

$Q_{n}$ has a useful decomposition in which its vertex set is partitions into
two sets $B_{n}=0B_{n-1}\cup 1B_{n-1}$, where $0B_{n-1}$ denotes the vertices
that start with a $0$ and $1B_{n-1}$ denotes the vertices that start with a
$1$. Using this decomposition we can write

$Q_{n}=0Q_{n-1}+1Q_{n-1}$

where $0Q_{n-1}$ and $1Q_{n-1}$ denote the induced subgraphs of $Q_{n}$ with
vertex sets $0B_{n-1}$ and $1B_{n-1}$ respectively, and $+$ denotes the
perfect matching between $0Q_{n-1}$ and $1Q_{n-1}$. Similarly, we have the
following fundamental decompositions for Fibonacci cubes, Lucas cubes and
Alternate Lucas cubes:

$\displaystyle\Gamma_{n}=0\Gamma_{n-1}+10\Gamma_{n-2}\,,{}$

where there is a perfect matching between $10\Gamma_{n-2}$ and
$00\Gamma_{n-2}\subset 0\Gamma_{n-1}$,

$\displaystyle\Lambda_{n}=0\Gamma_{n-1}+10\Gamma_{n-3}0\,,{}$

where there is a perfect matching between $10\Gamma_{n-3}0$ and
$00\Gamma_{n-3}0\subset 0\Gamma_{n-1}$,

$\displaystyle{\cal L}_{n}=0{\cal L}_{n-1}+10{\cal L}_{n-2}\,,{}$

where there is a perfect matching between $10{\cal L}_{n-2}$ and $00{\cal
L}_{n-2}\subset 0{\cal L}_{n-1}$.

###  2.1 Euler numbers

Following [18], a permutation $\sigma=\sigma_{1}\sigma\ldots\sigma_{n}$ of
$[n]$ is alternating if $\sigma_{1}>\sigma_{2},<\sigma_{3}>\sigma_{4}<\cdots$.
In other words, $\sigma_{i}<\sigma_{i+1}$ for $i$ even and $a_{i}>a_{i+1}$ for
$i$ odd. $\sigma$ is reverse alternating if
$\sigma_{1}<\sigma_{2}>\sigma_{3}<\sigma_{4}\cdots$. Let $E_{n}$ denote the
number of alternating permutations of $[n]$ with $E_{0}=1$. These are known as
the Euler numbers. The number of reverse alternating permutations of $[n]$ is
also given by $E_{n}$.

By a result of Désiré André [1], we have

$2E_{n+1}=\sum_{k=0}^{n}{n\choose k}E_{k}E_{n-k}\,,$

and the exponential generating function of the sequence of Euler numbers is
given by

$\displaystyle\sum_{n\geq 0}E_{n}\frac{x^{n}}{n!}$ $\displaystyle=$
$\displaystyle\sec x+\tan x$ $\displaystyle=$ $\displaystyle
1+x+\frac{x^{2}}{2!}+2\frac{x^{3}}{3!}+5\frac{x^{4}}{4!}+16\frac{x^{5}}{5!}+61\frac{x^{6}}{6!}+\cdots$

First few terms of Euler numbers (sequence A000111 in the OEIS [16]) are
$E_{0}=1$, $E_{1}=1$, $E_{2}=1$, $E_{3}=2$, $E_{4}=5$, $E_{5}=16$, $E_{6}=61$.

##  3 Calculation for the Fibonacci cubes

In this section we determine the number of diametral paths in $\Gamma_{n}$.
Since $n={\rm diam}(\Gamma_{n})$, these paths are of length $n$. $\Gamma_{n}$
is an induced subgraph of $Q_{n}$ with vertex set ${\cal FB}_{n}$. We have the
following easy result.

######  Proposition 1.

There is a unique pair of diametrically opposite vertices in $\Gamma_{n}$.
They are

  * (i)

$u=(01)^{\frac{n}{2}}$ and $v=(10)^{\frac{n}{2}}$ if $n$ is even,

  * (ii)

$u=(01)^{\frac{n-1}{2}}0$ and $v=(10)^{\frac{n-1}{2}}1$ if $n$ is odd.

Even though $\Gamma_{n}$ is undirected, here we view the edges on each such
path to be directed from $u$ to $v$. By direct inspection we have
$c(u,v;\Gamma_{1})=1$, $c(u,v;\Gamma_{2})=1$, $c(u,v;\Gamma_{3})=2$,
$c(u,v;\Gamma_{4})=5$, $c(u,v;\Gamma_{5})=16$. For a path

$u=s_{0}\rightarrow s_{1}\rightarrow\cdots\rightarrow s_{n}=v~{},$

each vertex $s_{i+1}$ is obtained from the vertex $s_{i}$ by flipping a 0 to a
1, or a 1 to a 0, with the proviso that no consecutive 1s appear in any
$s_{i}$. We see in particular that $c(u,v;\Gamma_{3})=2$ as there are two
paths of length 3 from $u$ to $v$ when $n=3$ as shown in the Table 1.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$
---|---|---|---
$v=s_{3}$ | 1 | 0 | 1
$s_{2}$ | 1 | 0 | 0
$s_{1}$ | 0 | 0 | 0
$u=s_{0}$ | 0 | 1 | 0

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$
---|---|---|---
$v=s_{3}$ | 1 | 0 | 1
$s_{2}$ | 0 | 0 | 1
$s_{1}$ | 0 | 0 | 0
$u=s_{0}$ | 0 | 1 | 0

Table 1: Two different paths from $u=010$ to $v=101$ in $\Gamma_{3}$.

Here we write $u$ in the bottom most row. The $i$th step shows the string
$s_{i}$ after $i$ edges on the path have been traversed. Note that in this
representation, the path proceeds from bottom up and the row indices are
increasing from bottom up as well.

By using this representation we give a bijective proof that the sequence of
the numbers of diametral paths in Fibonacci cubes is precisely the sequence of
Euler numbers.

######  Theorem 1.

Let $u,v\in\Gamma_{n}$ such that $d(u,v)=n$. Then for $n\geq 1$, we have

$c(u,v;\Gamma_{n})=E_{n}~{},$

where $E_{n}$ is the $n$th Euler number.

###### Proof.

We give a bijection between paths of length $n$ from $u$ to $v$ in ${\cal
FB}_{n}$ and alternating permutations $\sigma$ of $[n]$. The bijection is best
communicated by an example. Suppose $n=8$ and we are given the path from
$u=01010101$ to $v=10101010$ whose steps are shown in Table 2.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$ | $~{}b_{4}~{}$ | $~{}b_{5}~{}$ | $~{}b_{6}~{}$ | $~{}b_{7}~{}$ | $~{}b_{8}~{}$
---|---|---|---|---|---|---|---|---
$v=s_{8}$ | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0
$s_{7}$ | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0
$s_{6}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0
$s_{5}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{4}$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{3}$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1
$s_{2}$ | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
$s_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1
$u=s_{0}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1
Table 2: A path from diametrically opposite vertices $u=(01)^{4}$ to
$v=(10)^{4}$ in $\Gamma_{8}$.

As the first step, we mark the first appearance of 1 as we go up the table in
every column with an odd index. In Table 3 these entries are circled.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$ | $~{}b_{4}~{}$ | $~{}b_{5}~{}$ | $~{}b_{6}~{}$ | $~{}b_{7}~{}$ | $~{}b_{8}~{}$
---|---|---|---|---|---|---|---|---
$v=s_{8}$ | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0
$s_{7}$ | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0
$s_{6}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0
$s_{5}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{4}$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{3}$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1
$s_{2}$ | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
$s_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1
$u=s_{0}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1
Table 3: First appearance of 1 as we go up in every column with an odd index
is marked in the path from $u=(01)^{4}$ to $v=(10)^{4}$ in $\Gamma_{8}$.

Next, we mark the first appearance of 0 as we go up the table in every column
with an even index. Circling these entries gives Table 4.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$ | $~{}b_{4}~{}$ | $~{}b_{5}~{}$ | $~{}b_{6}~{}$ | $~{}b_{7}~{}$ | $~{}b_{8}~{}$
---|---|---|---|---|---|---|---|---
$v=s_{8}$ | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0
$s_{7}$ | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0
$s_{6}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0
$s_{5}$ | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{4}$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1
$s_{3}$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1
$s_{2}$ | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
$s_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1
$u=s_{0}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1
Table 4: First appearance of 0/1 as we go up in every column with an even/odd
index is marked in the path from $u=(01)^{4}$ to $v=(10)^{4}$ in $\Gamma_{8}$.

After this we record the corresponding step number in each column. For
instance column 1 gives 5, column 2 gives 4, etc. by reading the indices of
the corresponding rows. The resulting alternating permutation is below:

5 4 7 1 3 2 8 6

These steps are reversible. Suppose this time that $n=7$ and we are given the
alternating permutation $3~{}1~{}6~{}4~{}7~{}2~{}5$. We construct Table 5 in
which the odd numbered columns 1, 3, 5, 7 are assigned the label 1 in the rows
3, 6, 7, 5, which are the entries in the odd positions of the given
permutation. The even numbered columns 2, 4, 6 are assigned the label 0 in the
rows 1,4, 2, which are the entries in the even indexed positions of the given
permutation.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$ | $~{}b_{4}~{}$ | $~{}b_{5}~{}$ | $~{}b_{6}~{}$ | $~{}b_{7}~{}$
---|---|---|---|---|---|---|---
$v=s_{7}$ |  |  |  |  | 1 |  |
$s_{6}$ |  |  | 1 |  |  |  |
$s_{5}$ |  |  |  |  |  |  | 1
$s_{4}$ |  |  |  | 0 |  |  |
$s_{3}$ | 1 |  |  |  |  |  |
$s_{2}$ |  |  |  |  |  | 0 |
$s_{1}$ |  | 0 |  |  |  |  |
$u=s_{0}$ |  |  |  |  |  |  |
Table 5: First appearance of 0/1 in every column with an even/odd index in the
path from $u=(01)^{3}0$ to $v=(10)^{3}1$ in $\Gamma_{7}$ corresponding to the
alternating permutation $3~{}1~{}6~{}4~{}7~{}2~{}5$.

Now we fill in the odd indexed columns of this matrix by 0, up to the marked 1
in the column, followed by 0s all the way up; and we fill the even indexed
columns by 1 up to the marked 0 in the column, followed by 1s all the way up.
This results in the path of length $n=7$ from $u$ to $v$ shown in Table 6
corresponding to the alternating permutation $3~{}1~{}6~{}4~{}7~{}2~{}5$.

Step | $~{}b_{1}~{}$ | $~{}b_{2}~{}$ | $~{}b_{3}~{}$ | $~{}b_{4}~{}$ | $~{}b_{5}~{}$ | $~{}b_{6}~{}$ | $~{}b_{7}~{}$
---|---|---|---|---|---|---|---
$v=s_{7}$ | 1 | 0 | 1 | 0 | 1 | 0 | 1
$s_{6}$ | 1 | 0 | 1 | 0 | 0 | 0 | 1
$s_{5}$ | 1 | 0 | 0 | 0 | 0 | 0 | 1
$s_{4}$ | 1 | 0 | 0 | 0 | 0 | 0 | 0
$s_{3}$ | 1 | 0 | 0 | 1 | 0 | 0 | 0
$s_{2}$ | 0 | 0 | 0 | 1 | 0 | 0 | 0
$s_{1}$ | 0 | 0 | 0 | 1 | 0 | 1 | 0
$u=s_{0}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0
Table 6: The path from the diametrically opposite vertices $u=(01)^{3}0$ to
$v=(10)^{3}1$ in $\Gamma_{7}$ corresponding to the alternating permutation
$3~{}1~{}6~{}4~{}7~{}2~{}5$.

Considering now the general case, we see that going from $u$ to $v$ in $n$
steps, every bit in $u$ has to change exactly once. This means that the row
indices of the marked entries in the matrix in Table 4 is a permutation
$\sigma$ of $[n]$. Now consider an element $t=\sigma_{i}$ with odd $i$ with
$1<i<n$. This means that in step $t$ of the path, that is in $s_{t}$, the
entry in the $i$th column goes from 0 to 1. But since all of the vertices that
appear in the table as rows are Fibonacci strings. This means that in
$s_{t-1}$ the entries in columns $i-1$ and $i+1$ which are adjacent to the
entry at column $i$ must already be 0. Therefore these entries were flipped
from 1 to 0 in earlier steps. It follows that $\sigma_{i}>\sigma_{i+1}$ and
$\sigma_{i}>\sigma_{i-1}$. The two extreme cases with $i=1$ and $i=n$ are
handled the same way. Therefore $\sigma$ is an alternating permutation. The
other direction is proved similarly. ∎

##  4 Calculation for the Lucas cubes

It is shown in [15] that

${\rm diam}(\Lambda_{n})=\left\\{\begin{array}[]{ll}n&\mbox{for $n$
even}\,,\\\ n-1&\mbox{for $n$ odd}\,.\end{array}\right.$

We have

######  Proposition 2.

The number of diametrically opposite pair of vertices in $\Lambda_{n}$ is 1 if
$n$ is even and $n$ if $n$ is odd. They are

  * •

$(01)^{\frac{n}{2}}$ and $(10)^{\frac{n}{2}}$ if $n$ is even,

  * •

cyclic shifts of the pair $0(01)^{\frac{n-1}{2}}$ and $0(10)^{\frac{n-1}{2}}$
if $n$ is odd.

######  Remark 1.

Note that there is a typo in [15, Proposition 1]. For $n$ odd, the number of
pairs of vertices in $\Lambda_{n}$ at distance equal to the diameter is $n$,
not $n-1$.

Similar to the proof of Theorem 1 we obtain the following result for
$\Lambda_{n}$.

######  Theorem 2.

Let $u,v\in\Lambda_{n}$ such that $d(u,v)={\rm diam}(\Lambda_{n})$. Then for
$n\geq 2$, we have

$c(u,v;\Lambda_{n})=\left\\{\begin{array}[]{ll}\frac{n}{2}E_{n-1}&\mbox{for
$n$ even}\,,\\\ E_{n-1}&\mbox{for $n$ odd}\,.\end{array}\right.$

###### Proof.

Assume first that $n$ is even. By Proposition 2 we only need to consider the
vertices $u=(01)^{\frac{n}{2}}$ and $v=(10)^{\frac{n}{2}}$. Mimicking the
bijective proof of Theorem 1, we arrive at permutations $\sigma$ of $[n]$
satisfying $\sigma_{i}>\sigma_{i+1}$ for any odd index $i$ with $1\leq i<n$,
$\sigma_{i}>\sigma_{i-1}$ for any odd index $i$ with $1<i\leq n$ and the extra
condition $\sigma_{1}>\sigma_{n}$, since in $\Lambda_{n}$ we have $b_{1}\cdot
b_{n}=0$. This last requirement on $\sigma$ is easily verified by tracing the
first appearance of a 1 in the first and the last columns of the table of
paths that define the bijection for $\Gamma_{n}$. Therefore, $\sigma$ must be
a circular alternating permutation, and these were enumerated by Kreweras
[14].

For $n$ odd, assume that $u_{1}=0(01)^{\frac{n-1}{2}}$ and
$v_{1}=0(10)^{\frac{n-1}{2}}$. Then we know that $u_{1},v_{1}\in
0\Gamma_{n-1}$ and since $\Lambda_{n}=0\Gamma_{n-1}+10\Gamma_{n-3}0$ we have

$c(u_{1},v_{1};\Lambda_{n})=c(u_{1},v_{1};0\Gamma_{n-1})=E_{n-1}\,.$

Let $u_{i}$ and $v_{i}$ be the $i-1$ right cyclic shifts of the vertices
$u_{1}$ and $v_{1}$ for $i=2,\ldots,n$, respectively. Then for any shortest
path $P$ from $u_{1}$ to $v_{1}$, the $i-1$ right cyclic shifts of all the
vertices in $P$ gives a shortest path from $u_{i}$ to $v_{i}$ for all
$i\in\\{2,\ldots,n\\}$, which completes the proof. ∎

##  5 Calculation for the Alternate Lucas cubes

For any integer $n\geq 3$, it is shown in [9] that ${\rm diam}({\cal
L}_{n})=n-1$. We have

######  Proposition 3.

For any integer $n\geq 4$, the number of diametrically opposite pair of
vertices in ${\cal L}_{n}$ is $4$. For $n\geq 4$, they are

  * (i)

$u=0^{s}(10)^{k}001$ and $v=1^{s}(01)^{k}010$,

  * (ii)

$u=0^{s}(10)^{k}010$ and $v=1^{s}(01)^{k}001$,

  * (iii)

$u=0^{s}(10)^{k}100$ and $v=1^{s}(01)^{k}001$,

  * (iv)

$u=0^{s}(10)^{k}100$ and $v=1^{s}(01)^{k}010$,

where $n=2k+3+s$, $k$ is a nonnegative integer and $s\in\\{0,1\\}$.

######  Theorem 3.

Let $n=2k+3+s$, $k$ be a nonnegative integer and $s\in\\{0,1\\}$. For $n\geq
4$, we have

$c(0^{s}(10)^{k}100,1^{s}(01)^{k}001;{\cal
L}_{n})=c(0^{s}(10)^{k}100,1^{s}(01)^{k}010;{\cal L}_{n})=E_{n-1}$
$c(0^{s}(10)^{k}001,1^{s}(01)^{k}010;{\cal
L}_{n})=c(0^{s}(10)^{k}010,1^{s}(01)^{k}001;{\cal L}_{n})={n-1\choose
2}E_{n-3}\,.$

###### Proof.

We sketch the proof. As in the proof of Theorem 1, we need to consider the
permutations $\sigma$ of $[n]$ satisfying extra conditions depending on the
pair of vertices. We will give the proof for $n$ even ($s=1$) and only for the
pairs $u=0^{s}(10)^{k}100$ and $v=1^{s}(01)^{k}001$ and $u=0^{s}(10)^{k}001$
and $v=1^{s}(01)^{k}010$. The other cases can be obtained similarly.

For the pair $u=0(10)^{k}100$ and $v=1(01)^{k}001$ as we consider the shortest
paths we will not change the $(n-1)$st position since it is 0 for each vertex.
Therefore we need to consider the permutations $\sigma$ of
$[n]\setminus\\{n-1\\}$ satisfying $\sigma_{i}>\sigma_{i+1}$ for any odd index
$i$ with $1\leq i\leq n-3$, $\sigma_{i}>\sigma_{i-1}$ for any odd index $i$
with $1<i\leq n-3$ and $\sigma_{n}>\sigma_{n-2}$, since in ${\cal L}_{n}$ we
have $b_{n-2}\cdot b_{n}=0$. By setting $\tau_{i}=\sigma_{i}$ for
$i=1,\ldots,n-2$ and $\tau_{n-1}=\sigma_{n}$ we observe that $\tau$ is an
alternating permutation of $[n-1]$.

Now consider the pair $u=0(10)^{k}001$ and $v=1(01)^{k}010$. In the shortest
paths under consideration, we will not change the $(n-2)$nd position since it
is 0 for each vertex. Therefore we need to consider the permutations $\sigma$
of $[n]\setminus\\{n-2\\}$ satisfying $\sigma_{i}>\sigma_{i+1}$ for any odd
index $i$ with $1\leq i<n-3$, $\sigma_{i}>\sigma_{i-1}$ for any odd index $i$
with $1<i\leq n-3$ and $\sigma_{n-1}>\sigma_{n}$. By setting
$\tau_{i}=\sigma_{i}$ for $i=1,\ldots,n-3$ we observe that $\tau$ is an
alternating permutation of $[n-3]$ and we have ${n-1\choose 2}$ different
choices for $\sigma_{n-1},\sigma_{n}$ which gives the desired result. ∎

## Acknowledgement

The work of the second author is supported by BAP-SUK-2021-19737 of Hacettepe
University. This work is partially supported by TÜBİTAK under Grant No.
120F125.

## References

  * [1] D. André, Développement de sec x and tg x, C. R. Math. Acad. Sci. Paris 88, 965–979, 1879.
  * [2] I. Bezáková, A. Searns, On counting oracles for path problems, Proc. of the 29th International Symposium on Algorithms and Computation (ISAAC 2018) (2018), Article 56.
  * [3] I. Bezáková, A.J. Friedlander, Computing and sampling minimum $(s,t)$-cuts in weighted planar graphs in polynomial time Theor. Comput. Sci. 417, 2–11, 2012.
  * [4] J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci. (1987), 49–60.
  * [5] E. Cheng, J.W. Grossman, L. Lipták, K. Qiu, Z. Shen, Distance formula and shortest paths for the $(n,k)$-star graphs, Inform. Sci. 180 (9), 1671–1680, 2010.
  * [6] E. Cheng, J. W. Grossman, K. Qiu, Z. Shen, The number of shortest paths in the arrangement graph, Inform. Sci. 240, 191–204, 2013.
  * [7] E. Cheng, K. Qiu, Z. Shen, The number of shortest paths in the $(n,k)$-star graphs, W. Wu, O. Daescu (Eds.), Proc. 4th Int. Conf. Combinatorial Optimization and Applications, COCOA’2010 Part I, LNCS, vol. 6508, Springer, Kailua-Kona, HI (2010), 222–236.
  * [8] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik. 1, 269–271, 1959.
  * [9] Ö. Eğecioğlu, E. Saygı, Z. Saygı, Alternate Lucas Cubes, Internat. J. Found. Comput. Sci. 32, 871–899, 2021.
  * [10] F. García, J. Solano, I. Stojmenovic, M. Stojmenovic, Higher dimensional hexagonal networks, J. Parallel Distrib. Comput. 63 (11), 1164–1172, 2003.
  * [11] Y. Gong, Q.-P. Gu, An efficient oracle for counting shortest paths in planar graphs, Theor. Comput. Sci. 921, 75–85, 2022.
  * [12] W.-J. Hsu, Fibonacci cubes–a new interconnection technology, IEEE Trans. Parallel Distrib. Syst. 4, 3–12, 1993.
  * [13] J. Irving, A. Rattan, Factorizations of permutations into star transpositions, Discrete Math. 309 (6), 1435–1442, 2009.
  * [14] G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Mathématiques et sciences humaines 53, 5–30, 1976.
  * [15] E. Munarini, C.P. Cippo and N. Zagaglia Salvi, On the Lucas cubes, Fibonacci Quart. 39, 12–21, 2001.
  * [16] OEIS Foundation Inc. (2022), The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A000111
  * [17] L. Schwiebert, There is no optimal routing policy for the torus, Inform. Process. Lett. 83 (6), 331–336, 2002.
  * [18] R. P. Stanley, A Survey of Alternating Permutations, Contem. Math. 531, 165–196, 2010.