# Metallic cubes

Tomislav Došlić
University of Zagreb Faculty of Civil Engineering,
Zagreb, Croatia
and
Faculty of Information Studies, Novo Mesto, Slovenia
<EMAIL_ADDRESS>Luka Podrug
University of Zagreb Faculty of Civil Engineering,
Zagreb, Croatia
<EMAIL_ADDRESS>
###### Abstract

We study a recursively defined two-parameter family of graphs which generalize
Fibonacci cubes and Pell graphs and determine their basic structural and
enumerative properties. In particular, we show that all of them are induced
subgraphs of hypercubes and present their canonical decompositions. Further,
we compute their metric invariants and establish some Hamiltonicity
properties. We show that the new family inherits many useful properties of
Fibonacci cubes and hence could be interesting for potential applications. We
also compute the degree distribution, opening thus the way for computing many
degree-based topological invariants. Several possible directions of further
research are discussed in the concluding section.

##  1 Introduction

The hypercubes $Q_{n}$ are one of the best known and most researched graph
families. In spite of their simple definition - $Q_{n}$ it the $n$-the
Cartesian power of $K_{2}$ \- they have rich internal structure and pose many
non-trivial research problems. In recent years and decades they have been
studied, among other reasons, for their potential uses as processor
interconnection networks of low diameter. This advantage is, however, often
offset by rigid restrictions on the number of nodes (always a power of two),
prompting thus interest in more flexible architectures along the same general
lines. Two variations, the Fibonacci and the Lucas cubes, turned out to be
promising, giving rise to a large number of papers studying their various
properties. As it could be guessed from their names, the number of vertices in
such structures grows slower, with the $n$-th power of the Golden Ratio, hence
as $\left(\frac{1+\sqrt{5}}{2}\right)^{n}\approx 1.618^{n}$, offering more
flexibility while preserving desirable properties of hypercubes [3]. Hence the
number of vertices satisfies the simplest non-trivial three-term linear
recurrence $v_{n}=v_{n-1}+v_{n-2}$ for $n\geq 3$ with the initial conditions
$v_{0}=2,v_{2}=3$.

Both hypercubes and Fibonacci cubes have natural representations as graphs
whose vertices consist of binary strings, subject to some additional
restrictions in the case of Fibonacci cubes, two vertices being adjacent if
and only if the Hamming distance between the corresponding strings is equal to
one. Fibonacci cubes have attracted much attention and spawned a number of
generalizations, most of them leading to graphs with the number of vertices
counted by various types of higher-order Fibonacci numbers [4]. In a recent
paper by Munarini [11], the author considered a generalization of different
type, extending the alphabet over which the strings are constructed and
imposing some restrictions on the new element in the alphabet. (Previous
generalizations were mostly concerned with binary strings with various
restrictions on adjacencies of ones.) It turned out that the new graphs
exhibit many similarities with Fibonacci cubes. In particular, they share the
property of being partial cubes, hence isometric subgraphs of hypercubes.
Also, the number of vertices in his graphs satisfies a three-term linear
recurrence with constant coefficients. More precisely, it is given by the Pell
numbers, the sequence of nonnegative integers satisfying the three-term linear
recurrence $P_{n}=2P_{n-1}+P_{n-2}$, for $n\geq 2$, with the initial
conditions $P_{0}=1,P_{1}=2$. Hence he named the new graphs the Pell graphs.

In this paper we take further the line of research started by Munarini in [11]
and ask whether graphs with desirable properties of Fibonacci cubes and Pell
graphs could be obtained by further extending the alphabet underlying the
strings serving as their vertices. We found that the answer is positive. In
the rest of this paper we describe one possible generalization, the most
natural in our opinion, a recursively defined family of graphs which shares
many structural properties with previously considered partial cubes. Our
graphs are parameterized by two nonnegative integer parameters, one, $a$,
denoting the alphabet size, the other, $n$, denoting the step in the
construction. As the number of vertices of the graph obtained at the $n$-th
step of a construction for a fixed value of $a$ satisfies the three-term
linear recurrence $v_{n}=av_{n-1}+v_{n-2}$, we call the resulting graphs the
metallic cubes. We find the name informative, reflecting both their partial
cube nature and the asymptotic behavior of the number of vertices, expressed
via roots of the characteristic equation $x^{2}-ax-1=0$, known as metallic
means.

In the next section we give necessary definitions and references. Section 3 is
concerned with basic structural properties of metallic cubes. The results are
then used in Section 4 to compute the number of edges and the degree
distribution. Section 5 deals with metric properties, i.e., with diameter,
radius, center and periphery of metallic cubes. In section 6 we address and
partially answer their Hamiltonicity properties. The paper is concluded by a
short section summarizing our findings and indicating some possibilities for
further research.

##  2 Definitions and illustrations

The hypercube $Q_{n}$ is defined as follows: The set of vertices $V(Q_{n})$
consists of all binary strings of length $n$ and two vertices are adjacent if
they differ in a single bit, i.e., if one vertex can be obtained from the
other by replacing $0$ with $1$ or vice versa, only once. The Fibonacci cubes
$\Gamma_{n}$ are special subgraphs of hypercubes where the vertices are the
Fibonacci strings $\mathcal{F}_{n}$, defined as binary strings of length $n$
without consecutive ones. The number of vertices in Fibonacci cubes is counted
by the Fibonacci numbers, $V(\Gamma_{n})=F_{n+2}$. The Pell graphs
$\Pi_{n}^{a}$, introduced by Munarini [11] in 2019, are graphs whose vertices
are strings of length $n$ over the alphabet $\left\\{0,1,2\right\\}$ with
property that $2$ comes only in blocks of even length. Two vertices are
adjacent if one can be obtained from the other by replacing $0$ with $1$ or by
replacing block $11$ with block $22$. The vertices in this family are counted
by the Pell numbers. The Munarini’s paper inspired us to try to generalize
this idea by obtaining family of graphs whose numbers of vertices satisfy
recursive relation $s_{n}=a\cdot s_{n-1}+s_{n-2}$ for arbitrary non-negative
integer $a$ while preserving main properties of Pell graphs.

Let $a$ be a non-negative integer and let $\mathcal{S}_{a}$ denote the free
monoid containing $a+1$ generators $\left\\{0,1,2,\dots,a-1,0a\right\\}$. By a
string we mean an element of monoid $\mathcal{S}_{a}$, i.e., a word from
alphabet $\left\\{0,1,2,\dots,a-1,a\right\\}$ with property that letter $a$
can only appear in block $0a$. Other letters can appear arbitrary. For strings
$\alpha=x_{1}\cdots x_{n}$ and $\beta=y_{1}\cdots y_{m}$ we define their
concatenation in the usual way, $\alpha\beta=x_{1}\cdots x_{n}y_{1}\cdots
y_{m}$.

If $\mathcal{S}^{a}_{n}$ denotes the set of all elements from the monoid
$\mathcal{T}_{a}$ of length $n$, one can easily obtain recursive relation for
the cardinal number $s^{a}_{n}=\left|\mathcal{S}^{a}_{n}\right|$. A string of
length $n$ can end with any of letters $0,1,\dots,a-1$ and the rest of the
string can be formed in $s_{n-1}^{a}$ ways. If a string ends with the letter
$a$, that necessarily means that there is at least one zero in front of that
$a$, and the rest of the string can be formed in $s_{n-2}^{a}$ ways. Hence,
$s_{n}^{a}$ satisfies the recursive relation

$s^{a}_{n}=as^{a}_{n-1}+s^{a}_{n-2}$ (2.1)

with initial values $s^{a}_{0}=1$ and $s^{a}_{1}=a$.

Now let $\Pi_{n}^{a}$ denote a graph whose vertices are elements of the set
$\mathcal{S}^{a}_{n}$, i.e., $V\left(\Pi_{n}^{a}\right)=\mathcal{S}^{a}_{n}$
and for any $v_{1},v_{2}\in V\left(\Pi_{n}^{a,b}\right)$ we have
$\left(v_{1},v_{2}\right)\in E\left(\Pi_{n}^{a,b}\right)$ if and only if one
vertex can be obtained from the other by replacing a single letter $k$ with
$k+1$ for $0\leq k\leq a-1$. An alternative definition of adjacency can be
given via modified Hamming distance. For $\alpha=\alpha_{1}\cdots\alpha_{n}$
and $\beta=\beta_{1}\cdots\beta_{n}$ we define

$\overline{h}(\alpha,\beta)=\sum\limits_{k=1}^{n}|\alpha_{k}-\beta_{k}|.$

Then $\alpha$ and $\beta$ are adjacent if and only if
$\overline{h}(\alpha,\beta)=1$. As an example, Figure 1 shows graphs
$\Pi^{a}_{n}$ for $a=3$ and $n=1,2,3$.

$000$$010$$020$$001$$011$$021$$002$$012$$022$$100$$110$$120$$101$$111$$121$$102$$112$$122$$200$$210$$220$$201$$211$$221$$202$$212$$222$$003$$103$$203$$030$$031$$032$$00$$10$$20$$01$$11$$21$$02$$12$$22$$03$$0$$1$$2$
Figure 1: Graph $\Pi_{n}^{3}$ for $n=1$ (lower left), $2$ (upper left), $3$
(right).

From the definition of family $\Pi^{a}_{n}$ it is immediately clear that
$\Pi^{1}_{n}=\Gamma_{n-1}$ but $\Pi^{2}_{n}$ are not isomorphic to Pell
graphs. One possible generalization could be obtained using alphabet
$\left\\{0,1,\dots,a\right\\}$ where two vertices are adjacent if one can be
obtained from the other by replacing single letter $i$ with $i+1$ for $\leq
i\leq a-2$ or by replacing a block $(a-1)(a-1)$ with $aa$. This family of
graphs would be a straightforward generalization of Pell graphs as defined by
Munarini, and would inherit many of their properties. Instead of pursuing this
approach we opted for a generalization better suited to higher values of $a$
yielding along the way an alternative definition of Pell graphs and offering
numerous possibilities for comparisons. The difference is illustrated in
Figure 2, where it can be seen that, although similar, the graphs obtained
under two generalizations are not isomorphic, for vertex $111$ of Pell graph
shown in the left panel of Figure 2 has degree $5$, while the maximum degree
in $\Pi^{2}_{3}$ is $4$.

In Table 1 we show the number of vertices for few initial values of $a$ and
$n$. The Pell number appear as the second row, while the (shifted) Fibonacci
numbers appear in the first one. It can be observed that the rows of Table 1
grow exponentially, as the $n$-th powers of the corresponding metallic means,
while the elements in columns grow polynomially. In fact, since the number of
vertices of $\Pi^{a}_{n}$ is equal to

$|V(\Pi^{a}_{n})|=\sum\limits_{k\geq 0}\binom{n-k}{k}a^{n-2k},$

for a fixed $n$, we obtain that growth of the number of vertices is polynomial
with degree $n$.

$\begin{array}[]{r|cccccccc}{}_{a}\backslash^{n}&1&2&3&4&5&6&7&8\\\ \hline\cr
1&1&2&3&5&8&13&21&34\\\ 2&2&5&12&29&70&169&408&985\\\
3&3&10&33&109&360&1189&3927&12970\\\ 4&4&17&72&305&1292&5473&23184&98209\\\
5&5&26&135&701&3640&18901&98145&509626\\\
6&6&37&228&1405&8658&53353&328776&2026009\end{array}$

Table 1: Number of vertices in $\Pi^{a}_{n}$.

$000$$001$$101$$100$$010$$011$$111$$110$$022$$122$$221$$220$

$101$$111$$001$$011$$002$$100$$110$$000$$010$$102$$020$$021$

Figure 2: The Pell graph $\Pi_{3}$ (left) and the corresponding metallic cube
$\Pi^{2}_{3}$ (right).

##  3 Basic structural properties

###  3.1 Canonical decompositions and bipartivity

It is well known that Fibonacci cubes and Pell graphs admit recursive
decomposition [11]. In this section we show that such decompositions naturally
extend to metallic cubes.

We start with the observation that the set of vertices $\mathcal{S}_{n}^{a}$
can be divided into disjoint sets based of the starting letter. One set
contains the vertices starting with block $0a$, and the remaining $a$ sets
contain the vertices that start with $0,1,\dots,a-2$ and $a-1$, respectively.
Assuming $\alpha\in\mathcal{S}^{a}_{n-1}$ and $\beta\in\mathcal{S}^{a}_{n-2}$,
the vertices $0\alpha$, $1\alpha$, $\dots$, $(a-1)\alpha$ generate $a$ copies
of a graph $\Pi^{a}_{n-1}$ and vertices $0a\beta$ generate one copy of
$\Pi^{a}_{n-2}$. That brings us to our first result.

######  Theorem 1.

Metallic cube $\Pi^{a}_{n}$ admits the decomposition

$\Pi^{a}_{n}=\Pi^{a}_{n-1}\oplus\cdots\oplus\Pi^{a}_{n-1}\oplus\Pi^{a}_{n-2}$

in which the first factor $\Pi^{a}_{n-1}$ is repeated $a$ times.

The decomposition of Theorem 1 is called the canonical decomposition of
$\Pi^{a}_{n}$.

$0\alpha$$1\alpha$$2\alpha$$(a-1)\alpha$$\cdots$$0(a-1)\beta$$0a\beta$$P_{a}\square\Pi^{a}_{n-1}$$P_{2}\square\Pi^{a}_{n-2}$
Figure 3: Canonical decomposition
$\Pi^{a}_{n}=\Pi^{a}_{n-1}\oplus\cdots\oplus\Pi^{a}_{n-1}\oplus\Pi^{a}_{n-2}$.

In Figure 3 we show a schematic representation of the described canonical
decomposition. As an example, Figure 4 shows the canonical decomposition of
graph $\Pi_{3}^{3}$ into three copies of graph $\Pi_{2}^{3}$ and one copy of
graph $\Pi_{1}^{3}$.

It is worth noting that
$\Pi^{a}_{n-1}\oplus\cdots\oplus\Pi^{a}_{n-1}=P_{a}\square\Pi^{a}_{n-1}$,
where $P_{a}$ is the path graph on $a$ vertices.

A map $\chi:V(G)\to\left\\{0,1\right\\}$ is a proper $2$-coloring of a graph
$G$ if $\chi(v_{1})\neq\chi(v_{2})$ for every two adjacent vertices
$v_{1},v_{2}\in V(G)$. A graph $G$ is bipartite if its set of vertices $V(G)$
can be decomposed into two disjoint subsets such that no two vertices of the
same subset share an edge. Equivalently, a graph $G$ is bipartite if it admits
a proper $2$-coloring.

######  Theorem 2.

All metallic cubes are bipartite.

###### Proof.

Proof is by induction on $n$. We start by observing that $\Pi^{a}_{1}$ is
isomorphic to the path graph on $a$ vertices and, thus, bipartite. Since
$\Pi^{a}_{2}$ is an $a\times a$ grid with one additional vertex $0a$, it is an
easy exercise to see that it also admits a proper $2$-coloring. Now we suppose
that $\Pi^{a}_{k}$ is bipartite for every $k<n$. By the inductive hypothesis,
it admits a proper $2$-coloring $\chi:\Pi^{a}_{n-1}\to\left\\{0,1\right\\}$.
Consider the map $\chi^{\prime}:\Pi^{a}_{n-1}\to\left\\{0,1\right\\}$, where
$\chi^{\prime}(v)=1-\chi(v)$. Then the map $\chi^{\prime}$ is a complementary
proper $2$-coloring for graph $\Pi^{a}_{n-1}$. Since
$\Pi^{a}_{n}=\Pi^{a}_{n-1}\oplus\cdots\oplus\Pi^{a}_{n-1}\oplus\Pi^{a}_{n-2}$,
we can choose a coloring $\chi$ for subgraph $\Pi^{a}_{n-1}$ in $\Pi^{a}_{n}$
if the subgraph is induced by vertices starting with even $k$, and
$\chi^{\prime}$ if $k$ is odd. Finally, for the one copy of $\Pi^{a}_{n-2}$ in
the canonical decomposition, we can choose $\chi^{\prime}$ restricted to
$\Pi^{a}_{n-2}$. Thus we obtained a proper $2$-coloring of graph
$\Pi^{a}_{n}$. ∎

Figure 4 shows a proper $2$-coloring of graph $\Pi^{3}_{3}$.

$000$$010$$020$$001$$011$$021$$002$$012$$022$$100$$110$$120$$101$$111$$121$$102$$112$$122$$200$$210$$220$$201$$211$$221$$202$$212$$222$$003$$103$$203$$030$$031$$032$
Figure 4: The canonical decomposition and a proper $2$-coloring of
$\Pi_{3}^{3}=\Pi_{3}^{2}\oplus\Pi_{3}^{2}\oplus\Pi_{3}^{2}\oplus\Pi_{3}^{1}$.

As we have mentioned above, the sequence $s^{a}_{n}$ defined by recurrence
(2.1) satisfies the ell-known identity

$\displaystyle s^{a}_{n}=\sum\limits_{k\geq 0}\binom{n-k}{k}a^{n-2k}.$ (3.1)

We now present another decomposition of metallic cubes, providing a
combinatorial representation of identity (3.1). To this end, recall that
$P_{a}$ denotes a path graph with $a$ vertices, and $P_{a}^{k}$ denotes
Cartesian product of path $P_{a}$ with itself $k$ times, that is $P_{a}\square
P_{a}\cdots\square P_{a}$. Also note that $|V(P_{a}^{k})|=a^{k}$. Graphs
$P_{a}^{k}$ are called grids or lattices. The following theorem illustrates
the combinatorial meaning of the Fibonacci polynomials of identity (3.1).

######  Theorem 3.

Graph $\Pi^{a}_{n}$ can be decomposed into $F_{n+1}$ grids, where $F_{n}$
denotes $n$-th Fibonacci number.

###### Proof.

Consider the subset of strings $S\subset\mathcal{S}^{a}_{n}$ where each string
$\alpha\in S$ has $k$ blocks $0a$ in the same position. Then $\alpha$ has
$n-2k$ letters that are not part of a $0a$ block. There are $a^{n-2k}$ such
strings and the subset $S\subset\mathcal{S}^{a}_{n}$ induces a subgraph of
$\Pi^{a}_{n}$ isomorphic to grid $P_{a}^{n-2k}$ with $a^{n-2k}$ vertices. Also
note that different locations of blocks $0a$ produce different strings. Hence,
for different alignments, the induced grids are vertex-disjoint. To finish our
proof, we just need to determine the number of strings with exactly $k$ blocks
$0a$. We can identify block as a single letter, and reduce our problem to a
subset of $n-k$ positions, where we need to choose $k$ positions for blocks.
Thus, we have $\binom{n-k}{k}$ different alignments for $k$ blocks $0a$, and
every alignment induces disjoint subgraphs $P_{a}^{n-2k}$. We obtained a
decomposition

$\Pi^{a}_{n}=\bigoplus_{k\geq 0}\binom{n-k}{k}P^{n-2k}_{a}.$

Then the number of grids is $\sum\limits_{k\geq 0}\binom{n-k}{k}=F_{n+1}$, and
this completes our proof. ∎

To obtain our last result in this subsection, we consider the map
$\rho:V(\Pi^{a}_{n})\to\mathcal{F}_{n}$ defined on alphabet
$\left\\{0,1,\dots,a\right\\}$ and extended to $V(\Pi^{a}_{n})$ by
concatenation, as follows

$\rho(\alpha)=\begin{cases}0,&0\leq\alpha\leq a-1,\\\ 1,&\alpha=1.\end{cases}$

For a Fibonacci string $w$, let $\rho^{-1}(w)$ denote the subgraph of
$\Pi^{a}_{n}$ induced by vertices $\left\\{v\in
V(\Pi^{a}_{n})|\rho(v)=w\right\\}$.

######  Theorem 4.

Let $\Pi^{a}_{n}/\rho$ be the quotient graph of $\Pi^{a}_{n}$ obtained by
identifying all vertices which are identified by $\rho$, and two vertices
$w_{1}$ and $w_{2}$ in $\Pi^{a}_{n}/\rho$ are adjacent if there is at least
one edge in $\Pi^{a}_{n}$ connecting blocks $\rho^{-1}(w_{1})$ and
$\rho^{-1}(w_{2})$ Then $\Pi^{a}_{n}/\rho$ is isomorphic to the Fibonacci cube
$\Gamma_{n-1}$.

###### Proof.

The map $\rho$ identifies two vertices $v_{1},v_{2}\in\Pi^{a}_{n}$ if they
have the same number and the same positions of blocks $0a$. But all vertices
having equal number of $k$ blocks $0a$ in the same positions induce a grid
subgraph $P_{a}^{n-2k}$. So, each such grid is mapped into the single vertex
in $\Pi^{a}_{n}/\rho$. By Theorem 3, $|V(\Pi^{a}_{n}/\rho)|=F_{n+1}$. Two
grids have at least one edge connecting them if the number of $0a$ blocks
between them differ by exactly one, with the grid having one block less,
having all $0a$ blocks on same positions as the other grid. For example, for
$a=5$ and $n=5$, one grid $P^{1}_{5}$ is induced by vertices $\alpha 0505$ and
another grid $P^{3}_{5}$ is induced by vertices
$\beta_{1}05\beta_{2}\beta_{3}$, where
$\alpha,\beta_{1},\beta_{2},\beta_{3}\in\left\\{0,1,2,3,4\right\\}$. Then
those grids must have an edge connecting them. For example, the edge
connecting vertices $00504$ and $00505$. From the definition of map $\rho$ it
is clear that $\rho$ maps two grids in the neighboring vertices in
$\Pi^{a}_{n}/\rho$ only if their image by $\rho$ differs in a single bit.
Hence, $\Pi^{a}_{n}/\rho$ is isomorphic to $\Gamma_{n-1}$. ∎

$0001$$0101$$0100$$0000$$0011$$0111$$0110$$0010$$0002$$0102$$0021$$0020$$1001$$1101$$1100$$1000$$1011$$1111$$1110$$1010$$1002$$1102$$1021$$1020$$0201$$0200$$0210$$0211$$0202$
Figure 5: Decomposition of $\Pi_{4}^{2}=P^{4}_{2}\oplus P^{2}_{2}\oplus
P^{2}_{2}\oplus P^{2}_{2}\oplus P_{2}^{0}$.

###  3.2 Embedding into hypercubes

Since hypercubes $Q_{n}$ have binary strings as vertices, and all binary
strings of length $n$ are vertices in $\Pi_{n}^{a}$ for $a\geq 2$, we have a
natural inclusion $Q_{n}\subset\Pi^{a}_{n}$. Furthermore, for $a\geq 1$, since
$\mathcal{S}^{1}_{n}\subset\mathcal{S}^{a}_{n}$, for every $a$, we have
$\Gamma_{n-1}=\Pi^{1}_{n}\subseteq\Pi^{a}_{n}$. The following theorem shows
that every metallic cube is an induced subgraph of some Fibonacci cube.

######  Theorem 5.

For any $a\geq 1$ and $n\geq 1$, metallic cubes are induced subgraphs of
Fibonacci cubes and, hence, hypercubes.

###### Proof.

For $a=2$, we define a map $\sigma$ on primitive blocks, i.e., on the blocks
that every string from the set $\mathcal{S}^{2}_{n}$ can be uniquely
decomposed into, $0$, $1$, and $02$ as follows

$\displaystyle\sigma(0)$ $\displaystyle=001$ $\displaystyle\sigma(1)$
$\displaystyle=000$ $\displaystyle\sigma(02)$ $\displaystyle=001010.$

For $a>2$, primitive blocks, are $0,1,\dots,a-1$ and $0a$. So, we set

$\displaystyle\sigma(0)$ $\displaystyle=010101\cdots 010101$
$\displaystyle\sigma(1)$ $\displaystyle=000101\cdots 010101$
$\displaystyle\sigma(2)$ $\displaystyle=000001\cdots 010101$
$\displaystyle\vdots$ $\displaystyle\sigma(a-2)$ $\displaystyle=000000\cdots
000001$ $\displaystyle\sigma(a-1)$ $\displaystyle=000000\cdots 000000$
$\displaystyle\sigma(0a)$ $\displaystyle=010101\cdots 01010100100000\cdots
000000,$

where strings $\sigma(k)$ have length $2a-2$, for $0\leq k\leq a-1$ and string
$\sigma(0a)$ has length $4n-4$.

In case of $a=2$, the map $\sigma$, defined on primitive blocks, expands to
$\sigma:\Pi^{2}_{n}\to\Pi^{1}_{3n}$ by concatenation. In case of $a\geq 3$, it
expands to $\sigma:\Pi^{a}_{n}\to\Pi^{1}_{(2a-2)n}$. Since the map is
injective and preserves adjacency, we obtained an induced subgraph of
Fibonacci cube isomorphic to the graph $\Pi^{a}_{n}$. ∎

Next we show that metallic cubes are median graphs. A median of three vertices
is a vertex that lies on a shortest path between every two of three vertices.
We say that a graph $G$ is a median graph if every three vertices of $G$ have
unique median.

$00$$10$$20$$01$$11$$21$$02$$12$$22$$03$ Figure 6: Median of vertices $10$,
$22$ and $03$ is a vertex $12$ .

Figure 6 shows that the unique median of vertices $10$, $22$ and $03$ is
vertex $12$, because that is only vertex that lies in shortest paths between
every two red vertices.

Klavžar [5] proved that Fibonacci and Lucas cubes are median graphs, and
Munarini [11] proved that Pell graphs are median graphs. They both used the
following theorem by Mulder [10]:

######  Theorem 6 (Mulder).

A graph $G$ is median graph if and only if $G$ is a connected induced subgraph
of an $n$-cube such that with any three vertices of $G$ their median in
$n$-cube is also a vertex of $G$.

######  Theorem 7.

For all $a\geq 1$ and $n\geq 0$, $\Pi^{a}_{n}$ is a median graph.

###### Proof.

It is well known that the median of the triple in $Q_{n}$ is obtained by the
majority rule. So let $\alpha=\epsilon_{1}\cdots\epsilon_{n}$,
$\beta=\delta_{1}\cdots\delta_{n}$ and $\gamma=\rho_{1}\cdots\rho_{n}$ be
binary strings, i.e.,
$\epsilon_{i},\gamma_{i},\rho_{i}\in\left\\{0,1\right\\}$. Then their median
is $m=\zeta_{i}\cdots\zeta_{n}$, where $\zeta_{i}$ is equal to the number that
appears at least twice among the numbers $\epsilon_{i}$, $\gamma_{i}$ and
$\rho_{i}$.

Let $a\geq 3$ and let $\sigma$ be the map defined in the proof of Theorem 5.
By the same theorem, $\Pi^{a}_{n}$ is a connected induced subgraph of a
$(2a-2)n$-cube. To finish our proof, we just need to verify that the subgraph
induced by the set $\sigma\left(\mathcal{S}^{a}_{n}\right)$ is median closed,
i.e., that for every three vertices in
$\sigma\left(\mathcal{S}^{a}_{n}\right)$, their median is also a vertex in
$\sigma\left(\mathcal{S}^{a}_{n}\right)$. Every string from the set
$\sigma\left(\mathcal{S}^{a}_{n}\right)$ can be uniquely decomposed into
blocks $\sigma\left(j\right)$ with length $2a-2$, for $0\leq j\leq a-1$, and
block $\sigma\left(0a\right)$ with length $4a-4$. Note that the median of
three blocks, where two blocks are the same, is that block that appears at
least twice. Hence, we only need to consider cases where all three blocks are
different. First consider three blocks $\sigma\left(i\right)$,
$\sigma\left(j\right)$ and $\sigma\left(k\right)$. Without loss of generality
we can assume that $0\leq i<j<k\leq a-1$. Then their median is
$\sigma\left(j\right)$. In the second case we have $\sigma\left(i\right)$ and
$\sigma\left(j\right)$ for $0\leq i\leq j\leq a-1$, and the second half of the
block $\sigma\left(0a\right)$, i.e. of the string $0010\cdots 0$ with length
$(2a-2)n$. But, since one comes only in even positions in strings
$\sigma\left(i\right)$ and $\sigma\left(j\right)$, their median is
$\sigma\left(j\right)$. Also note that we do not have to consider a case with
the first half of the block $\sigma\left(0a\right)$, because it is equal to
the block $\sigma\left(a-1\right)$. So, we conclude that the subgraph induced
by set $\sigma\left(\mathcal{S}^{a}_{n}\right)$ is median closed. The proof
for $a=2$ is similar, so we omit the details. ∎

##  4 The number of edges and distribution of degrees

Now that we have elucidated the recursive structure of metallic cubes via the
canonical decomposition, the recurrences for the number of edges and the
details of degree distributions can be simply read off from our structural
results. We start with counting the edges of $\Pi^{a}_{n}$.

Let $e^{a}_{n}$ denote the number of edges in $\Pi^{a}_{n}$, i.e.,
$e^{a}_{n}=|E(\Pi^{a}_{n})|$. Since $\Pi^{a}_{0}$ is empty graph,
$e^{a}_{0}=0$. The graph $\Pi^{a}_{1}$ is the path graph with $a$ vertices,
so, we have $e^{a}_{1}=a-1$. The graph $\Pi^{a}_{2}$ is an $a\times a$ grid
with addition of vertex $0a$ being adjacent to vertex $0(a-1)$. Hence,
$e^{a}_{2}=a^{2}+1$. For larger values of $n$, the graph $\Pi^{a}_{n}$
consists of $a$ copies of $\Pi^{a}_{n-1}$ and a single copy of
$\Pi^{a}_{n-2}$, and those subgraphs contribute with $a\cdot
e^{a}_{n-1}+e^{a}_{n-2}$ edges. Furthermore, there are $(a-1)\cdot
s^{a}_{n-1}+s^{a}_{n-2}$ edges connecting $a$ subgraphs $\Pi^{a}_{n-1}$ and
one subgraph $\Pi^{a}_{n-2}$. Since
$s^{a}_{n}-s^{a}_{n-1}=(a-1)s^{a}_{n-1}+s^{a}_{n-2}$, the overall number of
edges is

$e^{a}_{n}=a\cdot e^{a}_{n-1}+e^{a}_{n-2}+s^{a}_{n}-s^{a}_{n-1}.$

Hence, the number of edges satisfies a non-homogeneous linear recurrence of
length 2 with the same coefficients in the homogeneous part as the recurrence
for the number of vertices. Table 2 shows some first few values of
$e^{a}_{n}$. With some care, patterns of the coefficients of the polynomials
appearing there can be analyzed, suggesting the explicit formula established
in our following theorem.

######  Theorem 8.

The number of edges in graph $\Pi^{a}_{n}$ is

$e^{a}_{n}=\sum_{k=0}^{n}(-1)^{n+k}\left\lceil\frac{n+k}{2}\right\rceil\binom{\left\lfloor\frac{n+k}{2}\right\rfloor}{k}a^{k}$

###### Proof.

We proceed by induction on $n$. For $n=1$ and $n=2$ the statement holds.
Furthermore, the number of vertices $s_{n}$ satisfy the well-known identity
$s^{a}_{n}=\sum\limits_{k\geq 0}\binom{n-k}{k}a^{n-2k}$. Then we have

$\displaystyle s^{a}_{n}-s^{a}_{n-1}$ $\displaystyle=\sum\limits_{k\geq
0}\binom{n-k}{k}a^{n-2k}-\sum\limits_{k\geq 0}\binom{n-k-1}{k}a^{n-2k-1}$
$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{k}\binom{n-\left\lceil\frac{k}{2}\right\rceil}{\left\lfloor\frac{k}{2}\right\rfloor}a^{n-k}$
$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{k}\binom{n-\left\lceil\frac{k}{2}\right\rceil}{n-k}a^{n-k}$
$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{n+k}\binom{n-\left\lceil\frac{n-k}{2}\right\rceil}{k}a^{k}$
$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{n+k}\binom{\left\lfloor\frac{n+k}{2}\right\rfloor}{k}a^{k}$

By using the inductive hypothesis, after adjusting indices and expanding the
range of summation, we obtain

$\displaystyle a\cdot e^{a}_{n-1}+e^{a}_{n-2}=$
$\displaystyle\sum_{k=0}^{n-1}(-1)^{n+k-1}\left\lceil\frac{n+k-1}{2}\right\rceil\binom{\left\lfloor\frac{n+k-1}{2}\right\rfloor}{k}a^{k+1}+$
$\displaystyle+\sum_{k=0}^{n-2}(-1)^{n+k}\left\lceil\frac{n+k-2}{2}\right\rceil\binom{\left\lfloor\frac{n+k-2}{2}\right\rfloor}{k}a^{k}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{n}(-1)^{n+k}\left\lceil\frac{n+k-2}{2}\right\rceil\binom{\left\lfloor\frac{n+k-2}{2}\right\rfloor}{k-1}a^{k}+$
$\displaystyle+\sum_{k=0}^{n}(-1)^{n+k}\left\lceil\frac{n+k-2}{2}\right\rceil\binom{\left\lfloor\frac{n+k-2}{2}\right\rfloor}{k}a^{k}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n}(-1)^{n+k}\left\lceil\frac{n+k-2}{2}\right\rceil\binom{\left\lfloor\frac{n+k}{2}\right\rfloor}{k}a^{k}$

Now, by using expressions for $s^{a}_{n}-s^{a}_{n-1}$ and $a\cdot
e^{a}_{n-1}+e^{a}_{n-2}$ our claim follows at once. ∎

$\begin{array}[]{r|l}n&e^{a}_{n}\\\ \hline\cr 1&a-1\\\ 2&2a^{2}-2a+1\\\
3&3a^{3}-3a^{2}+4a-1\\\ 4&4a^{4}-4a^{3}+9a^{2}-6a+1\\\
5&5a^{5}-5a^{4}+16a^{3}-12a^{2}+9a-1\\\ \end{array}$

Table 2: Number of edges in $\Pi^{a}_{n}$.

For Fibonacci cubes, Klavžar [5] proved that
$|E(\Gamma_{n})|=F_{n+1}+\sum_{k=1}^{n-2}F_{k}F_{n+1-k}$. By plugging in $a=1$
into our result and recalling that $\Pi^{1}_{n}=\Gamma_{n-1}$, we have
obtained a combinatorial proof of the following identity.

######  Corollary 1.

$\sum_{k=0}^{n}(-1)^{n+k}\left\lceil\frac{n+k}{2}\right\rceil\binom{\left\lfloor\frac{n+k}{2}\right\rfloor}{k}=\sum_{k=0}^{n}F_{k}F_{n-k}.$

Now we turn our attention to degrees of vertices of metallic cubes and to
their distribution. We consider first the case $a\geq 3$. Hence, let $a\geq 3$
and $v=\alpha_{1}\cdots\alpha_{n}\in\Pi^{a}_{n}$ be any vertex. If
$0<\alpha_{i}<a-1$ for all $i$, then $v$ has maximum possible degree, which is
$2n$. Each $0a$ block reduces the degree by $3$, each $0(a-1)$-block reduces
the degree by $1$, as well as each letter $0$ or $a-1$ which is not part of
some $0(a-1)$-block. We are interested in the number of vertices with degree
$2n-m$. So let $v$ be a vertex containing $l$ $0a$-blocks, $h$ $0(a-1)$-blocks
and $k$ letters $0$ or $a-1$, where none of $k$ letters $0$ and $a-1$ are part
of $0(a-1)$-block. Then $v$ has degree $2n-3l-h-k$. Now we want to count the
number of such vertices. There are
$\binom{n-h-l}{h}\binom{n-2h-l}{l}\binom{n-2h-2l}{k}$ ways to choose positions
of $0a$-blocks, $0(a-1)$-blocks and letters $0$ or $a-1$. The rest of
$n-2h-2l-k$ positions we can fill in $(a-2)^{n-2h-2l-k}$ ways. If we set that
there are $2^{k}$ ways to fill $k$ positions with $0$ or $a-1$, we possibly
obtained more that $l$ $0(a-1)$-blocks and counted some vertices more than
once. Let
$q(n,l,h,k)=q(l,k)=\binom{n-h-l}{h}\binom{n-2h-l}{l}\binom{n-2h-2l}{k}2^{k}(a-2)^{n-2h-2l-k}$
denote the number of vertices where all vertices with exactly $l$ blocks are
counted once, and vertices with more then $l$ blocks are counted more then
once. More precisely, beside vertices of length $l$, number $q(l)$ counts all
vertices with $l+1,l+2,\dots l+\left\lfloor\frac{k}{2}\right\rfloor$ blocks
$0(a-1)$, where each vertex with exactly $l+j$ blocks is counted
$\binom{l+j}{l}$ times. If $p(n,l,h,k)=p(l,k)$ denotes the number of vertices
with precisely $l$ blocks $0(a-1)$, we have

$\displaystyle
q(l,k)=\sum\limits_{j=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\binom{l+j}{l}p(l+j,k-2j).$

Now we retrieve the numbers $p(l,k)$ by direct counting. To obtain the number
of vertices with exactly $l$ blocks, we have to subtract the number of
vertices with more than $l$ blocks. Vertices having $l+1$ block were counted
$\binom{l+1}{l}$ times in $q(l,k)$ and subtracting
$q(l,k)-q(l+1,k-2)\binom{l+1}{l}$ corrects that error. But then the vertices
containing $l+2$ blocks were counted
$\binom{l+2}{l}-\binom{l+2}{l+1}\binom{l+1}{l}=\binom{l+2}{l}$ times so far,
so we need to add $\binom{l+2}{l}q(l+2,k-4)$ to cancel that error.
Inductively, vertex with $l+j$ blocks is counted

$\displaystyle\binom{l+j}{j}-\sum\limits_{s=0}^{j-1}\binom{l+j}{l+s}\binom{l+s}{l}$
$\displaystyle=\binom{l+j}{j}-\binom{l+j}{l}\sum\limits_{s=0}^{j-1}\binom{s}{j}$
$\displaystyle=\begin{cases}0&\textup{ for }j\textup{ odd}\\\
-2\binom{l+j}{j}&\textup{ for }j\textup{ even}\end{cases}$

times, and there are $q(l+j,k-2j)$ such vertices. So we conclude that the
number of vertices that have exactly $l$ blocks $0(a-1)$ is

$\displaystyle
p(l,k)=\sum_{j=0}^{\left\lfloor\frac{k}{2}\right\rfloor}(-1)^{j}\binom{l+j}{j}q(l+j,k-2j).$
(4.1)

Let $\Delta_{n,m}$ denotes the overall number of vertices of degree $m$. Then
we have

$\displaystyle\Delta_{n,2n-m}$
$\displaystyle=\sum_{\begin{subarray}{c}3h+l+k=m\\\ 2h+2l+k\leq n\\\ l,h,k\geq
0\end{subarray}}p(n,h,l,k).$

The maximum degree is achieved for $m=0$. Then formula (4.1) reduces itself to
$\Delta_{n,2n}=(a-2)^{n}$. The minimum degree is achieved for the largest
possible number of $0a$-blocks, which reduce degree the most, hence
$l=\left\lfloor\frac{n}{2}\right\rfloor$ and
$k=n-2\left\lfloor\frac{n}{2}\right\rfloor$. Thus
$m=n+\left\lfloor\frac{n}{2}\right\rfloor$. The formula for
$\Delta_{n,\left\lceil\frac{n}{2}\right\rceil}$ reduces to

$\displaystyle\Delta_{n,\left\lceil\frac{n}{2}\right\rceil}$
$\displaystyle=q\left(n,\left\lfloor\frac{n}{2}\right\rfloor,0,n-2\left\lfloor\frac{n}{2}\right\rfloor\right)$
$\displaystyle=\left(\binom{n-\left\lfloor\frac{n}{2}\right\rfloor}{\left\lfloor\frac{n}{2}\right\rfloor}2^{n-2\left\lfloor\frac{n}{2}\right\rfloor}\right)(a-2)^{0}$
$\displaystyle=\begin{cases}1&\textup{for }n\textup{ even;}\\\ n+1&\textup{for
}n\textup{ odd.}\end{cases}$

Figure 7 shows degree of each vertex in graphs $\Pi^{3}_{1}$, $\Pi^{3}_{2}$
and $\Pi^{3}_{3}$.

$3$$4$$4$$4$$5$$5$$4$$4$$4$$4$$5$$4$$5$$6$$5$$5$$5$$4$$3$$4$$3$$4$$5$$4$$4$$4$$3$$2$$3$$2$$2$$3$$2$$2$$3$$2$$3$$4$$3$$3$$3$$2$$1$$1$$2$$1$
Figure 7: Graph $\Pi_{n}^{3}$ for $n=1,2,3$ with degree of each vertex.

It is now time to consider the cases $a=1$ and $a=2$. Their separate treatment
is necessary since, for $a=2$, there are no letters beside $0,a-1$ and $a$ and
for $a=1$ we only have $0$ and $a$. For $a=2$ we have $k=n-2h-2l$ and
$q(n,h,l,k)$ becomes

$q(n,h,l)=\binom{n-h-l}{h}\binom{n-2h-l}{l}2^{n-2h-2l},$

and the rest of the argument is the same. The maximum degree is now obtained
by setting $l=\left\lfloor\frac{n}{2}\right\rfloor$ and $h=0$. The minimum
degree is obtained by setting $h=\left\lfloor\frac{n}{2}\right\rfloor$ and
$l=0$. Since both cases produce the same number of vertices, we have

$\displaystyle\Delta_{n,\left\lceil\frac{n}{2}\right\rceil}=\Delta_{n,n+\left\lfloor\frac{n}{2}\right\rfloor}$
$\displaystyle=q\left(n,0,\left\lfloor\frac{n}{2}\right\rfloor\right)$
$\displaystyle=\left(\binom{n-\left\lfloor\frac{n}{2}\right\rfloor}{\left\lfloor\frac{n}{2}\right\rfloor}2^{n-2\left\lfloor\frac{n}{2}\right\rfloor}\right)$
$\displaystyle=\begin{cases}1&\textup{for }n\textup{ even;}\\\ n+1&\textup{for
}n\textup{ odd.}\end{cases}$

For $a=1$, we would need to modify our approach, but we omit the details since
distribution of degrees for Fibonacci cubes is already available in the
literature [8].

We conclude this section by computing the bivariate generating functions for
two-indexed sequences $\Delta_{n,k}$ counting the number of vertices in
$\Pi_{n}^{a}$ with exactly $k$ neighbors. We suppress $a$ in order to simplify
the notation. Take $a\geq 2$. Recall that $\mathcal{T}_{a}$ denotes the set of
all words from alphabet $\left\\{0,1,2,\dots,a-1,a\right\\}$ with property
that letter $a$ can only appear immediately after $0$. Every letter starts
with $0,\dots a-1$ or with the block $0a$. Hence, set $\mathcal{T}_{a}$ can be
decomposed into disjoint subsets based on starting letters. We write

$\mathcal{T}_{a}=\epsilon+0\mathcal{T}_{a}+1\mathcal{T}_{a}+\cdots+(a-1)\mathcal{T}_{a}+0a\mathcal{T}_{a},$

where $\epsilon$ denotes the empty word. Let
$\Delta(x,y)=\sum\limits_{n,k}\Delta_{n,k}x^{n}y^{k}$ be a formal power series
where $\Delta_{n,k}$ is the number of vertices of length $n$ having $k$
neighbors. Let $\mathcal{T}^{0}_{a}$ contain all vertices that start with $0$,
but not with $0a$-block and let $\Delta^{0}(x,y)$ denote corresponding formal
series. Then we have

$\displaystyle\Delta(x,y)$
$\displaystyle=1+\Delta^{0}(x,y)+(a-2)xy^{2}\Delta(x,y)+xy\Delta(x,y)+x^{2}y\Delta(x,y)$
$\displaystyle\Delta^{0}(x,y)$
$\displaystyle=xy\left(1+\Delta^{0}(x,y)+(a-1)xy^{2}\Delta(x,y)+x^{2}y\Delta(x,y)\right)$

Note that adding $0$ at the beginning of a vertex increases the number of
neighbors by one, except when the vertex starts with $a-1$, in which case
adding $0$ increases the number of neighbors by two. By solving the above
system of equations we readily obtain the generating function:

$\Delta(x,y)=\dfrac{1}{1-(2y+(a-2)y^{2})x-(y-y^{2}+y^{3})x^{2}}.$

For the reader’s convenience, we list some first few values of $\Delta_{n,k}$
in Table 3. It is interesting to observe that their rows are not unimodal.
Also, they do not (yet) appear in the On-Line Encyclopedia of Integer
Sequences [13].

$\begin{array}[]{cl}a=2&\begin{array}[]{c|ccccccc}n\backslash
k&1&2&3&4&5&6&7\\\ \hline\cr 1&2&0&0&0&0&0&0\\\ 2&1&3&1&0&0&0&0\\\
3&0&4&4&4&0&0&0\\\ 4&0&1&10&7&10&1&0\\\ 5&0&0&6&20&18&20&6\\\
\end{array}\\\\[43.05542pt] a=3&\begin{array}[]{c|cccccccccc}n\backslash
k&1&2&3&4&5&6&7&8&9&10\\\ \hline\cr 1&2&1&0&0&0&0&0&0&0&0\\\
2&1&3&5&1&0&0&0&0&0&0\\\ 3&0&4&6&14&8&1&0&0&0&0\\\
4&0&1&10&19&33&34&11&1&0&0\\\ 5&0&0&6&23&60&85&108&63&14&1\\\
\end{array}\end{array}$

Table 3: Some first values of $\Delta_{n,k}$ for $a=2$ and $a=3$.

The obtained bivariate generating functions could be further used to obtain
the average values and higher order moments of the degree distributions, but
we leave the details to the interested reader.

##  5 Metric properties

In this section we look at some metric-related properties of metallic cubes.
In particular, for a given metallic cube $\Pi_{n}^{a}$ we compute its radius
and diameter and determine its center and periphery as functions of $a$ and
$n$.

A path of length $n$ in graph is a sequence of $n$ edges
$e_{1},e_{2},\cdots,e_{n}$ such that $e_{i}$ and $e_{i+1}$ have common vertex
for every $1\leq i\leq n-1$. The distance between any two vertices
$v_{1},v_{2}\in V(G)$, denoted by $d(v_{1},v_{2})$, is the length of any
shortest path between them. By eccentricity $e(v)$ of a vertex $v\in V(G)$ we
mean the distance from $v$ to any vertex farthest from it. More precisely,
$e(v)=\max_{w\in V(G)}d(v,w)$. The radius of $G$, denoted by $r(G)$, is the
minimum eccentricity of the vertices, and diameter of $G$, denoted by $d(G)$,
is the maximum eccentricity over all vertices of $G$. A vertex $v$ is central
if $e(v)=r(G)$. The subset $Z(G)=\left\\{v\in V(G):e(v)=r(G)\right\\}\subset
V(G)$ is called the center of $G$, while the subset $P(G)=\left\\{v\in
V(G):e(v)=r(G)\right\\}\subset V(G)$ is called the periphery of $G$. In the
next few theorems, we determine radius, center, diameter and periphery of
metallic cubes.

######  Remark 1.

Let $v=\alpha_{1}\cdots\alpha_{n}\in V(\Pi^{a}_{n})$ be an arbitrary vertex.
To reach a vertex most distanced from $v$, every letter in $v$ greater than
$\left\lfloor\frac{a}{2}\right\rfloor$ must be changed into $0$. Any letter
smaller than $\left\lfloor\frac{a}{2}\right\rfloor$ must be changed to $a-1$
or, if the letter before it was changed to $0$, into $a$. A letter equal to
$\left\lfloor\frac{a}{2}\right\rfloor$ must be changed to $0$ unless the
letter before it was changed into $0$, in which case it must be changed into
$a$.

######  Theorem 9.

For $a\geq 1$ and $n\geq 1$ we have

$\displaystyle
r(\Pi^{a}_{n})=\left\lfloor\frac{a}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{a}{2}\right\rceil\left\lfloor\frac{n}{2}\right\rfloor.$
(5.1)

###### Proof.

Let $\epsilon=\left\lfloor\frac{a}{2}\right\rfloor$ and
$\hat{\epsilon}=\epsilon\epsilon\cdots\epsilon\in V(\Pi^{a}_{n})$. We want to
compute the eccentricity $e(\hat{\epsilon})$. It is not hard to see that any
longest path from $\epsilon$ leads to the vertex $0a0a\cdots 0$ if $n$ is odd,
or to $0a0a\cdots 0a$ if $n$ is even. Note that the most distant vertex of
$\hat{\epsilon}$ does not have to be unique. Single letter $\epsilon$ can be
changed to $0$ in $\left\lfloor\frac{a}{2}\right\rfloor$ steps, and to $a$ in
$a-\left\lfloor\frac{a}{2}\right\rfloor=\left\lceil\frac{a}{2}\right\rceil$
steps. Since $\hat{\epsilon}$ has length $n$, there are
$\left\lceil\frac{n}{2}\right\rceil$ odd positions and
$\left\lfloor\frac{n}{2}\right\rfloor$ even positions. That brings us to the
total of
$\left\lfloor\frac{a}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{a}{2}\right\rceil\left\lfloor\frac{n}{2}\right\rfloor$
steps. Thus,
$e(\epsilon\epsilon\cdots\epsilon)=\left\lfloor\frac{a}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{a}{2}\right\rceil\left\lfloor\frac{n}{2}\right\rfloor$.

As the next step, we want to show that every other vertex has eccentricity at
least $e(\epsilon)$. Let $v\in V(\Pi^{a}_{n})$ be arbitrary. If $v$ has $k$
blocks $0a$, then it has $n-2k$ letters in alphabet $0,1,\dots,a-1$. The most
distant vertex is obtained if we change every single letter $0,1,\dots,a-1$ in
string $v$ at least $\left\lfloor\frac{a}{2}\right\rfloor$ times, and if we
change each block $0a$ into $(a-1)0$. The latter transition requires $k(2a-1)$
steps.

To prove that
$e(v)\geq\left\lfloor\frac{a}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{a}{2}\right\rceil\left\lfloor\frac{n}{2}\right\rfloor$,
we will consider cases of even and odd $a$ separately. If $a$ is even, then
formula (5.1) becomes $r(\hat{\epsilon})=n\cdot\frac{a}{2}$. Hence,

$\displaystyle
e(v)\geq(n-2k)\cdot\frac{a}{2}+k(2a-1)=n\cdot\frac{a}{2}+k(a-1)\geq
n\cdot\frac{a}{2}=e(\hat{\epsilon}).$

For $a$ odd, formula 5.1 reduces to
$r(\hat{\epsilon})=n\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{2}\right\rfloor\right)$.
We have to prove that changing arbitrary number of letters in $\hat{\epsilon}$
does not decrease the eccentricity. So, let $k$ denote the number of letters
that differ from $\epsilon$. That leaves us with $s$ blocks of $\epsilon$ of
length $h_{1},h_{2}\dots,h_{s}$. Note that $n=k+\sum h_{i}$ and $s\leq k+1$.
According to the first part of the proof, each $\epsilon$-block contributes to
eccentricity with
$h_{i}\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)$,
and each $\alpha\neq\epsilon$ contributes at least with $\frac{a+1}{2}$. Note
that block $0a$ contributes more than any two letters, so we can assume $v$
does not contain $0a$ blocks. We have

$\displaystyle e(v)$
$\displaystyle\geq\sum\left(h_{i}\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)\right)+k\cdot\frac{a+1}{2}$
$\displaystyle=n\cdot\frac{a}{2}-\frac{1}{2}\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)+\frac{k}{2}$
$\displaystyle\geq n\cdot\frac{a}{2}+\frac{k-s}{2}$ $\displaystyle\geq
n\cdot\frac{a}{2}-\frac{1}{2}.$

Hence, for odd $n$, we have $e(v)\geq e(\hat{\epsilon})$. For even $n$, we
have to show that
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)\leq
k$. If
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)=k+1$,
each $h_{i}$ is odd and $s$ and $k$ have different parity. If $s$ is odd, then
$\sum h_{i}$ is odd, and since $n=\sum h_{i}+k$, $k$ is odd too. It follows
that $s$ is even. Then $\sum h_{i}$ is even and $k$ is even too. Thus, we
reached contradiction with
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)=k+1$.
It follows that
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)\leq
k$, and

$\displaystyle e(v)$ $\displaystyle\geq
n\cdot\frac{a}{2}-\frac{1}{2}\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)+\frac{k}{2}$
$\displaystyle\geq n\cdot\frac{a}{2}$ $\displaystyle=e(\hat{\epsilon}).$

∎

######  Corollary 2.

For $a$ and $n$ odd, the center of $\Pi_{n}^{a}$ consists of a single vertex,
$Z(\Pi^{a}_{n})=\left\\{\hat{\epsilon}\right\\}$.

###### Proof.

Let $a$ and $n$ be odd and let
$\epsilon=\left\lfloor\frac{a}{2}\right\rfloor=\frac{a-1}{2}$. By Theorem 9,
we have $R(\Pi^{a}_{n})=n\cdot\frac{a}{2}-\frac{1}{2}$ and $\hat{\epsilon}\in
Z(\Pi^{a}_{n})$. Suppose $v\in Z(\Pi^{a}_{n})$. We want to prove that
$v=\hat{\epsilon}$. As in the proof of Theorem 9, let $h_{1},\cdots,h_{s}$
denote the length of $\epsilon$ blocks in $v$, and let $k$ denotes the number
of letters $\alpha\neq\epsilon$. Since $v\in Z(\Pi^{a}_{n})$, contributions of
$\epsilon$-blocks and letters between them must be minimal. Minimal
contribution of each letter $\alpha\neq\epsilon$ is $\frac{a+1}{2}$, which is
achieved only by changing $\epsilon+1$ into $0$ or $\epsilon-1$ into $a-1$.
Hence, $\alpha=\epsilon\pm 1$. Minimal contribution of each $\epsilon$-blocks
is
$h_{i}\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)$.
We have:

$\displaystyle e(v)$
$\displaystyle=\sum\left(h_{i}\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)\right)+k\cdot\frac{a+1}{2}$
$\displaystyle=n\cdot\frac{a}{2}-\frac{1}{2}\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)+\frac{k}{2}$
$\displaystyle=n\cdot\frac{a}{2}-\frac{1}{2}.$

It follows that
$\frac{1}{2}\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)-\frac{k}{2}=\frac{1}{2}$,
so we conclude that
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)=s=k+1$.
That means that the length of $\epsilon$-blocks must be odd and between every
two blocks there is a single letter $\alpha_{i}$ different from $\epsilon$. So
$v$ has the form
$\hat{\epsilon}_{1}\alpha_{1}\cdots\hat{\epsilon}_{k}\alpha_{k}\hat{\epsilon}_{k+1}$.
The first $\epsilon$-block must be changed into $0a0\cdots 0a0$, hence
$\alpha_{1}$ must be $\epsilon+1$, which, by changing into $0$ contributes
$\frac{a+1}{2}$. Otherwise, $\alpha_{1}=\epsilon-1$ could be changed into $a$,
and contribution would be increased by one. But then, in order to achieve
maximal distance, block $\hat{\epsilon_{2}}$ must be changed into $a0a0a\cdots
0a$, which is contradiction with minimality of the contribution. That means
$k=0$, and $v=\epsilon$. ∎

Let $\epsilon=\left\lfloor\frac{a}{2}\right\rfloor$ and
$\hat{\epsilon}=\epsilon\cdots\epsilon\in V(\Pi^{a}_{n})$, as before. We
define $U^{a}_{n}\subseteq V(\Pi^{a}_{n})$ to be the set containing all
vertices such that

  1. 1.

they differ from $\hat{\epsilon}$ in at most one position, i.e., they have
form $\epsilon\cdots\epsilon\alpha\epsilon\cdots\epsilon$, where
$\alpha=\epsilon$ or $\alpha=\epsilon\pm 1$,

  2. 2.

letter $\epsilon+1$ can only appear on even positions,

  3. 3.

letter $\epsilon-1$ can only appear on odd positions.

Note that for an even $n$, every vertex $v\in U^{a}_{n}$ not equal to
$\hat{\epsilon}$ has exactly one $\epsilon$-block of odd length.

######  Corollary 3.

For $a$ odd and $n$ even, $Z(\Pi^{a}_{n})=U_{n}^{a}$.

###### Proof.

By Theorem 9, $\hat{\epsilon}\in Z(\Pi^{a}_{n})$, so let $v\in U^{a}_{n}$ be
arbitrary and different from $\hat{\epsilon}$. Let $h_{1}$ denote the length
of odd $\epsilon$-block and, since $n$ is even, the other $\epsilon$-block has
even length $h_{2}$. If $v$ has one letter $\epsilon+1$, then $\epsilon+1$ is
immediately after $\epsilon$-block of length $h_{1}$. So, by the proof of
Theorem 9, $\epsilon$-block of length $h_{1}$, by changing into block
$0a0\cdots 0a0$, contributes with $h_{1}\cdot\frac{a}{2}-\frac{1}{2}$, letter
$\epsilon+1$ contributes with $\frac{a+1}{2}$ by changing into $0$, and
$\epsilon$-block of length $h_{2}$ contributes with $h_{2}\cdot\frac{a}{2}$ by
changing into block $a0\cdots a0$. So,

$\displaystyle e(v)$
$\displaystyle=h_{1}\cdot\frac{a}{2}-\frac{1}{2}+\frac{a+1}{2}+h_{2}\cdot\frac{a}{2}=n\cdot\frac{a}{2},$

hence $v\in Z(\Pi^{a}_{n})$. In the other case, where $v$ contains letter
$\epsilon-1$ just before $\epsilon$-block of length $h_{1}$, we have similar
situation. Letter $\epsilon-1$ is either first letter or comes immediately
after $\epsilon$-block of length $h_{2}$. In both cases it must be changed
into $a-1$, thus contributing with $\frac{a+1}{2}$. The $\epsilon$-block of
length $h_{2}$ contributes with $h_{2}\cdot\frac{a}{2}$ by changing into
$0a\cdots 0a$, and $\epsilon$-block of length $h_{1}$ contributes with
$h_{1}\cdot\frac{a}{2}-\frac{1}{2}$. Thus, we proved $U^{a}_{n}\subseteq
Z(\Pi^{a}_{n})$.

Now we want to prove that $Z(\Pi^{a}_{n})\subseteq U^{a}_{n}$. Let $v\in
Z(\Pi^{a}_{n})$. Then $e(v)=n\cdot\frac{a}{2}$. On the other hand, let $k$
denote number of letters different from $\epsilon$. Those letters must be
$\epsilon\pm 1$, since every other letter increases the eccentricity. If
$h_{1},\dots,h_{s}$ denote the length of $\epsilon$-blocks, then

$\displaystyle e(v)$
$\displaystyle=\sum\left(h_{i}\cdot\frac{a}{2}-\frac{1}{2}\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)\right)+k\cdot\frac{a+1}{2}$
$\displaystyle=n\cdot\frac{a}{2}-\frac{1}{2}\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)+\frac{k}{2}.$

It follows that
$\sum\left(\left\lceil\frac{h_{i}}{2}\right\rceil-\left\lfloor\frac{h_{i}}{2}\right\rfloor\right)=k$,
which means that the number of $\epsilon$-blocks of odd length is $k$. If
$k=0$, then $v=\hat{\epsilon}$. If $k=1$, then there are at most two
$\epsilon$-blocks with lengths $h_{1}$ and $h_{2}$. Since $\epsilon+1$ coming
before $\epsilon$-block of odd length increases its eccentricity, we conclude
that it must come after it. In the other case, for the same reason, the letter
$\epsilon-1$ must come before $\epsilon$-block of odd length. Since $n$ is
even, the other $\epsilon$-block has even length. So, $v\in U^{a}_{n}$. If
$k>1$, then
$v=\hat{\epsilon_{1}}\alpha_{1}\cdots\hat{\epsilon_{k}}\alpha_{k}\epsilon_{k+1}$,
where $k$ blocks have odd length and one block has even length. Since $k>1$,
we have at least one substring
$\hat{\epsilon_{i}}\alpha_{i}\hat{\epsilon_{j}}$ with both $\epsilon$-blocks
of odd length. Since $\alpha_{i}$ must be $\epsilon+1$, it increases the
eccentricity of block $\hat{\epsilon_{j}}$. Hence, $k\leq 1$ and $v\in
U^{a}_{n}$. ∎

Let $\epsilon=\frac{a}{2}$ and let $V^{a}_{n}\subseteq Z(\Pi^{a}_{n})$ be the
set containing all vertices with letters $\epsilon$ or $\epsilon-1$ such that
$\epsilon-1$ can not appear after an $\epsilon$-block of odd length.

######  Corollary 4.

For $a$ even, $Z(\Pi^{a}_{n})=V^{a}_{n}$.

###### Proof.

Let $a$ be even and let $\epsilon=\frac{a}{2}$. By Theorem 9, we have
$R(\Pi^{a}_{n})=n\cdot\frac{a}{2}$ and $\hat{\epsilon}\in Z(\Pi^{a}_{n})$. Let
$v\in Z(\Pi^{a}_{n})$. Minimal contribution of each letter is $\frac{a}{2}$.
For minimal contribution to be achieved, one can only change letter
$\frac{a}{2}$ into $0$ or $a$, and $\frac{a}{2}-1$ into $a-1$. For letter
$\frac{a}{2}-1$ to be changed into $a-1$, the letter just before it must be
changed into $a-1$ or $a$. So, letter $\frac{a}{2}-1$ can come only after
another letter $\frac{a}{2}-1$ or after an $\epsilon$-block of even length.
Hence, $v\in V_{n}$.

Conversely, from definition of $V^{a}_{n}$, it is easy to see that
$e(v)=n\cdot\frac{a}{2}$ whenever $v\in V^{a}_{n}$, hence $V^{a}_{n}\subset
Z(\Pi^{a}_{n})$.∎

For example,
$Z(\Pi^{5}_{6})=\left\\{122222,221222,222212,222222,222223,222322,232222\right\\}$,
$Z(\Pi^{5}_{7})=\left\\{2222222\right\\}$ and
$Z(\Pi^{4}_{4})=\left\\{1111,1112,1122,1221,1222,2211,2212,2222\right\\}$.

######  Remark 2.

$|Z(\Pi^{a}_{n})|=\begin{cases}1&\textup{for }a\textup{ and }n\textup{ odd,
}\\\ n+1&\textup{for }a\textup{ odd and }n\textup{ even,}\\\
F_{n+2}&\textup{for }a\textup{ even.}\end{cases}$

Our final result in this section is about diameters of metallic cubes.

######  Theorem 10.

For $a\geq 1$ and $n\geq 0$ we have

$\displaystyle d(\Pi^{a}_{n})=an-1.$ (5.2)

The periphery consists of two vertices, $0a0a\cdots 0a(0)$ and $(a-1)0a\cdots
a0(a)$.

###### Proof.

Consider the vertex $v=0a0a\cdots 0$ if $n$ is odd or $v=0a0a\cdots a$ if $n$
is even. The first letter contributes with $a-1$ by changing into $a-1$, and
every other letter with $a$ by changing into $0$ or $a$. We have $e(v)=an-1$.
It is clear that no other vertex has eccentricity greater then $an-1$, because
a string can not begin with a letter $a$, thus maximal contribution of the
first letter is also achieved. So for $n$ even we have
$P(\Pi^{a}_{n})=\left\\{0a\cdots 0a,(a-1)0a\cdots a0\right\\}$, and for $n$
odd $P(\Pi^{a}_{n})=\left\\{0a\cdot a0,(a-1)0a\cdots 0a\right\\}$. ∎

$6$$6$$7$$5$$5$$6$$6$$5$$6$$6$$5$$6$$5$$4$$5$$6$$5$$5$$7$$6$$7$$6$$5$$6$$7$$6$$6$$7$$7$$8$$8$$7$$7$$4$$4$$5$$3$$3$$4$$4$$3$$4$$5$$2$$1$$2$
Figure 8: Graphs $\Pi_{n}^{3}$ for $n=1,2,3$ with eccentricity of every
vertex.

##  6 Hamiltonicity

A Hamiltonian path in a graph $G$ is a path that visits each vertex of $G$
exactly once. A Hamiltonian cycle in $G$ is a cycle that visits each vertex
exactly once. A graph containing a Hamiltonian cycle is called Hamiltonian
graph. In this section we examine some Hamiltonicity-related properties of
metallic cubes.

In their paper [9], Liu et al. showed that all (generalized) Fibonacci cubes
contain a Hamiltonian path. In the next theorem we show that every metallic
cube contains a Hamiltonian path.

######  Theorem 11.

For all $a,n\geq 1$, $\Pi^{a}_{n}$ contains a Hamiltonian path.

###### Proof.

Proof is by induction on $n$. We first consider the case of $a$ even. We wish
to prove that, not only $\Pi^{a}_{n}$ contains Hamiltonian path, but it
contains a path starting at $0a\cdots 0a(0)$ and ending at $(a-1)\cdots(a-1)$.
For $n=1$, graph $\Pi^{a}_{1}$ is path on $a$ vertices and the claim is
obviously valid. For $n=2$, graph $\Pi^{a}_{2}$ is an $a\times a$ grid with
addition of one vertex $0a$ being adjacent to the vertex $0(a-1)$. So, for
even $a$, a Hamiltonian path is $0a\to\cdots\to 00\to 10\to\cdots\to
1(a-1)\to\cdots\to(a-1)(a-1)$. Figure 9 shows a Hamiltonian path in
$\Pi^{2}_{2}$ and in $\Pi^{3}_{2}$. Now suppose that $\Pi^{a}_{n}$ contains a
Hamiltonian path for all $k<n$. By assumption, let $H_{n-1}$ and $H_{n-2}$
denote Hamiltonian paths in $\Pi^{a}_{n-1}$ and $\Pi^{a}_{n-2}$, respectively.
Paths $H_{n-1}$ and $H_{n-2}$ have starting point $0a0a\cdots 0a(0)$ and end-
point at $(a-1)\cdots(a-1)$. Let $0H_{n-1},\dots,(a-1)H_{n-1}$ and $0aH_{n-2}$
denote paths is $\Pi^{a}_{n}$ obtained from $H_{n-1}$ and $H_{n-2}$ by
appending $0,1,\dots,a-1$ or $0a$ on each vertex and let
$0\overline{H}_{n-1},\dots,(a-1)\overline{H}_{n-1}$ and $0a\overline{H}_{n-2}$
denote their reverse paths, i.e., paths starting at $(a-1)\cdots(a-1)$ and
ending at $0a\cdots 0a(0)$. Path $0aH_{n-2}$ ends at $0a(a-1)\cdots(a-1)$ and
path $0\overline{H}_{n-1}$ begins at $0(a-1)\cdots(a-1)$. Since vertices
$0a(a-1)\cdots(a-1)$ and $0(a-1)\cdots(a-1)$ are adjacent in $\Pi^{a}_{n}$,
those two paths can be concatenated. Hence, by concatenating
$0aH_{n-2},0\overline{H}_{n-1},1H_{n-1},\cdots,(a-2)\overline{H}_{n-1}$ and
$(a-1)H_{n-1}$, we obtain a Hamiltonian path in $\Pi^{a}_{n}$ that begins at
$0a\cdots 0a(0)$ and ends at $(a-1)\cdots(a-1)$.

Let $a$ now be odd. Now we wish to prove that $\Pi^{a}_{n}$ contains a
Hamiltonian path with endpoints at $0a(a-1)\cdots 0a(a-1)$ and
$(a-1)0a\cdots(a-1)0a$. For example, if $a=3$ and $n=1,2,3,4,5$, the end
points are $0$, $2$, $03$, $20$, $032$, $203$, $0320$, $2032$, $03203$ and
$20320$, respectively. The rest of the proof is carried out for $n$ where
$n\mod 3=0$. Cases for $n\mod 3=1$ or $2$ are similar, so we omit the details.
The base of induction is easy to check, similar as for even $a$. By
assumption, let $H_{n-1}$ and $H_{n-2}$ denote Hamiltonian paths in
$\Pi^{a}_{n-1}$ and $\Pi^{a}_{n-2}$, respectively. Path $H_{n-1}$ has the
starting point $0a(a-1)0a(a-1)\cdots 0a$ and the end-point
$(a-1)0a(a-1)0a\cdots(a-1)0$, and path $H_{n-2}$ starts at
$0a(a-1)0a(a-1)\cdots 0$ and ends at $(a-1)0a(a-1)0a\cdots(a-1)$. Let
$0H_{n-1},\dots,(a-1)H_{n-1}$ and $0aH_{n-2}$ denote paths in $\Pi^{a}_{n}$
obtained from $H_{n-1}$ and $H_{n-2}$ by appending $0,1,\dots,a-1$ and $0a$,
respectively, on each vertex and let
$0\overline{H}_{n-1},\dots,(a-1)\overline{H}_{n-1}$ and $0a\overline{H}_{n-2}$
denote their reverse paths, with start- and end-points switched. Path
$0aH_{n-2}$ ends at $0a(a-1)\cdots 0a(a-1)$ and path $0\overline{H}_{n-1}$
begins at $0(a-1)0a\cdots(a-1)0$. Since vertices $0a(a-1)\cdots 0a(a-1)$ and
$0(a-1)0a\cdots(a-1)0$ are adjacent in $\Pi^{a}_{n}$, those two paths can be
concatenated. Hence, by concatenating
$0aH_{n-2},0\overline{H}_{n-1},1H_{n-1},2\overline{H}_{n-1}\cdots,(a-2)H_{n-1}$
and $(a-1)\overline{H}_{n-1}$, we obtain a Hamiltonian path in $\Pi^{a}_{n}$
that begins at $0a(a-1)\cdots 0a(a-1)$ and ends at $(a-1)0a\cdots(a-1)0a$. ∎

As an example, Figure 10 shows Hamiltonian paths in $\Pi^{2}_{4}$ and in
$\Pi^{3}_{4}$.

$01$$00$$11$$10$$02$

$00$$10$$20$$01$$11$$21$$02$$12$$22$$03$

Figure 9: Hamiltonian path of $\Pi_{2}^{2}$ and $\Pi_{2}^{3}$.

$0001$$0101$$0100$$0000$$0011$$0111$$0110$$0010$$0002$$0102$$0021$$0020$$1001$$1101$$1100$$1000$$1011$$1111$$1110$$1010$$1002$$1102$$1021$$1020$$0201$$0200$$0210$$0211$$0202$

$2000$$2010$$2020$$2001$$2011$$2021$$2002$$2012$$2022$$2100$$2110$$2120$$2101$$2111$$2121$$2102$$2112$$2122$$2200$$2210$$2220$$2201$$2211$$2221$$2202$$2212$$2222$$2003$$2103$$2203$$2030$$2031$$2032$$1000$$1010$$1020$$1001$$1011$$1021$$1002$$1012$$1022$$1100$$1110$$1120$$1101$$1111$$1121$$1102$$1112$$1122$$1200$$1210$$1220$$1201$$1211$$1221$$1202$$1212$$1222$$1003$$1103$$1203$$1030$$1031$$1032$$0000$$0010$$0020$$0001$$0011$$0021$$0002$$0012$$0022$$0100$$0110$$0120$$0101$$0111$$0121$$0102$$0112$$0122$$0200$$0210$$0220$$0201$$0211$$0221$$0202$$0212$$0222$$0003$$0103$$0203$$0030$$0031$$0032$$0300$$0310$$0320$$0301$$0311$$0321$$0302$$0312$$0322$$0303$

Figure 10: Hamiltonian paths in $\Pi_{4}^{2}$ (above) and in $\Pi_{4}^{3}$
(below).

For $a$ even, the numbers $s^{a}_{2n+1}$ are even and $s^{a}_{2n}$ are odd. On
the other hand, for $a$ odd, the numbers $s^{a}_{3n+1}$ are even, but
$s^{a}_{3n}$ and $s^{a}_{3n+2}$ are odd. A simple consequence of Theorem 11 is
the following result on the existence of perfect and semi-perfect matchings in
metallic cubes.

######  Corollary 5.

Graph $\Pi^{a}_{n}$ admits a perfect matching if the number of vertices is
even, otherwise it admits a semi-perfect matching.

Now we examine the existence of Hamiltonian cycles in metallic cubes.

######  Theorem 12.

For even $a$ and $n$ odd, graphs $\Pi^{a}_{n}$ are Hamiltonian graphs.

###### Proof.

Let $a$ be even. Then $\Pi^{a}_{2}$ is an $a\times a$ grid with additional
vertex $0a$. It is easy to see that grids $a\times a$ contain a Hamiltonian
cycle, which implies that graph $\Pi^{a}_{2}$ contains a cycle that visits all
vertices but one, namely, the vertex $0a$. Now we wish to construct a
Hamiltonian cycle in graphs $\Pi^{a}_{3}$. Graph $\Pi^{a}_{3}$ can be
decomposed into $a$ copies of graph $\Pi^{a}_{2}$ and one copy of graph
$\Pi^{a}_{1}$. By Theorem 11, there exists a Hamiltonian path in each subgraph
$\Pi^{a}_{2}$ and $\Pi^{a}_{1}$. Let $0H_{2},1H_{2},\dots,(a-1)H_{2}$ and
$0aH_{1}$ denote those paths. Connecting starting points in $0H_{2}$ and
$1H_{2}$, as well as the ending points in $0H_{2}$ and $1H_{2}$ yields a cycle
in $0\Pi^{a}_{2}\oplus 1\Pi^{a}_{2}$. Since the number of copies of graph
$\Pi^{a}_{2}$ is even, we can pair up those copies to obtain $\frac{a}{2}$
cycles in the same manner. Now choose vertices $1v,1w\in 1\Pi^{a}_{2}$ so that
the edge $(1v)(1w)$ is in Hamiltonian cycle in $1\Pi^{a}_{2}$, and the
corresponding vertices $2v$ and $2w$ in $\Pi^{a}_{2}$. By removing edges
$(1v)(1w)$ and $(2v)(2w)$ from the cycles in $1\Pi^{a}_{2}$ and $2\Pi^{2}$ and
by adding edges $(1v)(2v)$ and $(1w)(2w)$, we obtain a Hamiltonian cycle for
subgraph $0\Pi^{a}_{2}\oplus 1\Pi^{a}_{2}\oplus 2\Pi^{a}_{2}\oplus
3\Pi^{a}_{2}$. This method is applicable between every two $\frac{a}{2}$
cycles. Thus, we obtained Hamiltonian cycle in $P_{a}\square\Pi^{a}_{2}$.
Since $\Pi^{a}_{1}$ is path graph with even number of vertices and, by Theorem
11 and construction so far, the path $0(a-1)H^{a}_{1}\subset 0H^{a}_{2}$ is a
part of a Hamiltonian cycle in $P_{a}\square\Pi^{a}_{2}$. Hence, we can extend
a Hamiltonian cycle in $P_{a}\square\Pi^{a}_{2}$ to $\Pi^{a}_{3}$ by adding a
zig-zag shape path to include all vertices of $\Pi^{a}_{1}$. Figure 11 shows a
Hamiltonian cycle for $a=2$ and $a=4$, but it is clear that construction can
be done whenever $a$ is even.

$000$$010$$001$$011$$002$$100$$110$$101$$111$$102$$020$$021$

$000$$010$$020$$030$$001$$011$$021$$031$$002$$012$$022$$032$$003$$013$$023$$033$$004$$100$$110$$120$$130$$101$$111$$121$$131$$102$$112$$122$$132$$103$$113$$123$$133$$104$$200$$210$$220$$230$$201$$211$$221$$231$$202$$212$$222$$232$$203$$213$$223$$233$$204$$300$$310$$320$$330$$301$$311$$321$$331$$302$$312$$322$$332$$303$$313$$323$$333$$304$$040$$041$$042$$043$

Figure 11: Hamiltonian cycle in $\Pi_{3}^{2}$ and in $\Pi_{3}^{4}$.

Now we wish to prove that every metallic cube contains a Hamiltonian cycle
when $a$ is even and $n$ is odd, and contains a cycle that visits all vertices
but one when both $a$ and $n$ are even. The proofs for $n$ even and odd are
similar, so we present just a proof for odd $n$. Since
$\Pi^{a}_{n}=P_{a}\square\Pi^{a}_{n-1}\oplus\Pi^{a}_{n-2}$, by assumption of
induction, there is cycle in each copy $\Pi^{a}_{n-1}$ that visits all
vertices but one. Let $k\Pi^{a}_{n-1}$ denote the copy of graph
$\Pi^{a}_{n-1}$ induced by the vertices that start with $k$, where $0\leq
k\leq a-1$. Let $\alpha\in\mathcal{S}^{a}_{n-1}$ and let $k\alpha$ denote
those vertices omitted by Hamiltonian cycle in each subgraph $k\Pi^{a}_{n-1}$,
$0\leq k\leq a-1$. Furthermore, by assumption, there is Hamiltonian cycle in
$\Pi^{a}_{n-2}$. Now we choose $\beta,\gamma\in\mathcal{S}^{a}_{n-1}$ so that
vertices $k\alpha$ and $k\beta$ are adjacent in $k\Pi^{a}_{n-1}$ and that the
edge $(k\beta)(k\gamma)$ is part of Hamiltonian cycle in $k\Pi^{a}_{n-1}$. For
$k=0,2,4,\dots,a-2$, we remove the edge $(k\beta)(k\gamma)$ and add edges
$(k\beta)(k\alpha)$, $(k\alpha)((k+1)\alpha)$, $((k+1)\alpha)(k+1)\beta$ and
$(k\gamma)(k+1)\gamma$. Thus we obtained Hamiltonian cycles in
$k\Pi^{a}_{n-1}\oplus(k+1)\Pi^{a}_{n-1}$. To merge those $\frac{a}{2}$ cycles
and one cycle in $\Pi^{a}_{n-2}$ together, we can choose any two corresponding
edges that are part of Hamiltonian cycles in the neighboring subgraphs and
apply similar method to merge all cycles in Hamiltonian cycle of graph
$\Pi^{a}_{n}$. Choosing corresponding edges is possible, for construction of
Hamiltonian cycle in this manner is inductive, hence, if some edge is part of
Hamiltonian cycle in one copy of $\Pi^{a}_{n-1}$, then it is part of
Hamiltonian cycle in all copies of $\Pi^{a}_{n-1}$. Similar observation holds
for supgraphs $0\Pi^{a}_{n-1}$ and $0a\Pi^{n-2}$. Figure 12 schematically
shows the described method of construction Hamiltonian cycles in
$\Pi^{a}_{n}$.

$0\beta$$0\gamma$$0\alpha$$1\gamma$$1\beta$$1\alpha$$2\beta$$2\gamma$$2\alpha$$3\gamma$$3\beta$$3\alpha$$0a\Pi^{a}_{n-2}$$0\Pi^{a}_{n-1}$$1\Pi^{a}_{n-1}$$2\Pi^{a}_{n-1}$$3\Pi^{a}_{n-1}$$\cdots$
Figure 12: Construction of a Hamiltonian cycle.

∎

##  7 Concluding remarks

In this paper we have introduced and studied a family of graphs generalizing,
on one hand, the Fibonacci and Lucas cubes, and, on the other hand, the Pell
graphs introduced recently by Munarini [11]. Their name, the metallic cubes,
reflects the fact that they are induced subgraphs of hypercubes and that their
number of vertices $v_{n}$ satisfies two-term recurrences,
$v_{n}=av_{n-1}+v_{n-2}$, whose (larger) characteristic roots are known as the
metallic means. We have investigated their basic structural, enumerative and
metric properties and settled some Hamiltonicity-related questions. Our
results show that the new generalization preserves many interesting properties
of the Fibonacci, Lucas, and Pell cubes, indicating thusly their potential
applicability in all related settings. Our results, however, are far from
presenting a comprehensive portrait of the new family. In order to keep this
contribution at a reasonable length, we have opted for presenting just the
basic results, without following all directions they open. For example, our
results on degree distribution open the possibility to compute many degree-
based topological invariants, while our results on distances do the same for
distance-based invariants such as, e.g., the Wiener and the Mostar index [6,
7, 2]. Our results on degrees could be further developed by looking at
irregularity, in the way ref. [14] does for Pell graphs. Similarly, apart from
a short comment about perfect and semi-perfect matchings, we have not
exploited our decomposition results to investigate any of matching-,
independence- and dominance-related problems that have been studied for
hypercubes and for Fibonacci and Lucas cubes. Work on some of the mentioned
problems is under way, and we plan to report on it in subsequent papers.

## Acknowledgments

Partial support of Slovenian ARRS (Grant no. J1-3002) is gratefully
acknowledged by T. Došlić.

## References

  * [1] F. Buckley, F. Harary,  Distance in Graphs,  Addison-Wesley, Redwood City, 1990.
  * [2] T. Došlić, I. Martinjak, R. Škrekovski, S. T. Spužević, I. Zubac,  Mostar index,  Math. Chem. 56 (2018) 2995–3013.
  * [3] W. J. Hsu,  Fibonacci cubes: A new class of interconnection topologies for parallel processing,  IEEE Trans. Parallel and Distributed Systems 4 (1993) 3–12.
  * [4] W. J. Hsu, M. J. Chung,  Generalized Fibonacci cubes,  Proc. Int’l Conf. Parallel Processing (1993) 299–303.
  * [5] S. Klavžar,  On median nature and enumerative properties of fibonacci-like cubes,  Discrete Math. 299 (2005) 145–153.
  * [6] S. Klavžar, M. Mollard,  Wiener Index and Hosoya Polynomial of Fibonacci and Lucas Cubes,  MATCH Commun. Math. Comput. Chem. 68 (2012) 311–324.
  * [7] S. Klavžar, M. Mollard,  Asymptotic Properties of Fibonacci Cubes and Lucas Cubes,  Ann. Combin. 18 (2014) 447–457.
  * [8] S. Klavžar, M. Mollard, and M. Petkovšek,  The degree sequence of Fibonacci and Lucas cubes,  Discrete Math. 311 (2001) 1310–1322.
  * [9] J. Liu, W. J. Hsu, M. J. Chung,  Generalized Fibonacci cubes are mostly Hamiltonian,  J. Graph Theory 18 (1994) 817–829.
  * [10] M. Mulder,  The structure of median graphs,  Discrete Math. 24 (1978) 197–204.
  * [11] E. Munarini,  Pell graphs,  Discrete Math. 342 (2019) 2415–2428.
  * [12] E. Munarini, N. Z. Salvi  Structural and enumerative properties of the Fibonacci cubes,  Discrete Math. 255 (2022) 317–324
  * [13] OEIS Foundation Inc. (2023),  The On-Line Encyclopedia of Integer Sequences,  Published electronically at https://oeis.org.
  * [14] A. Taranenko,  Irregularity of expansions and Pell graphs,  arXiv:2103.08177v1, preprint.


Geomagnetism and Aeronomy, 2020, Vol. 60, No. 7 LONG-TERM ACTIVITY IN
PHOTOSPHERES OF LOW-MASS STARS WITH STRONG MAGNETIC FIELDS N. I. Bondar’1*, M.
M. Katsova2** stars: activity – stars: cycles – stars: starspots – techniques:
photometry The behavior of the average annual luminosity of K–M dwarfs OU Gem,
EQ Vir, V1005 Ori and AU Mic was studied at time intervals of several decades.
The main sources of photometric data for 1989–2019 were the Hipparcos, ASAS,
KWS databases. An analysis of long-term series showed that the average annual
brightness of all stars varies cyclical. The durations of possible cycles for
OU Gem, V1005 Ori and AU Mic are 40–42 years, for EQ Vir – 16.6 years, and
amplitudes of cycles are of 0.09–0.2m. The selected stars belong to the group
of red dwarfs for which the average surface magnetic field $\langle B\rangle$
exceeds of several kilogauss. We examined the type of the relationship between
the parameters of the cycle, its duration and amplitude, for 9 stars with
$\langle B\rangle<4\;$kG. A tendency to increasing of the amplitude and
duration of the cycle when the value of $\langle B\rangle$ decrease has been
noted. It may be suggested that with an increasing of the surface magnetic
field, it becomes more uniform and the level of activity changes in this case
in less degrees than on stars with strong local fields concentrated in large
spots.

###### Contents

  1. 1 INTRODUCTION
  2. 2 LONG-TERM LIGHT CURVES AND  PHOTOMETRIC DATA SOURCES
  3. 3 SEARCH FOR POSSIBLE CYCLES IN  PHOTOSPHERES OF THE SELECTED STARS
  4. 4 ACTIVITY CYCLES AND MAGNETIC FIELDS
  5. 5 CONCLUSION

##  1 INTRODUCTION

Study the activity of main sequence stars is fundamental importance of both
for understanding the development and scales of active phenomena, nature of
their generation, as well as some the related to stellar activity issues
concerning to studying planets, the origin of life (a habitable zone), large-
scale cataclysms, an existence of civilizations.

At present, the instrumental capabilities make it possible to determine the
activity indices of G–K stars in all layers of the atmosphere and to measure
their magnetic fields. Dynamo processes occurring in the convection zone lead
to an increase of the magnetic field and its exit to the surface and in upper
layers of the atmosphere.

The relationship of parameters of active regions with the physical parameters
of stars and rotation has been well studied for solar-type stars with periods
of more than 5 days (Baliunas et al., 1995; Oláh et al., 2016; Distefano et
al., 2017). On fast-rotating stars with magnetic fields of about 4 kG and
more, the activity is less studied, but it has been established that for such
strong magnetic fields the relationship between rotation and activity level is
disrupt, and an increasing of the rotation does not lead to increase activity
indices, i.e., a saturation level is reached (Reiners et al., 2009; Shulyak et
al., 2017; 2019). Photometric data for fast-rotating stars were obtained for
limited time intervals and for a small set of stars. Currently, in connection
with the search for exoplanets, the photometric behavior of M dwarfs is being
actively studied, but in most cases it is data for 7–15 years (Savanov, 2012;
Suárez Mascareño et al., 2016; Distefano et al., 2017; Ibañez Bustos et al.,
2019). The convective zone of M-dwarfs is deeper than in G–K dwarfs, and
dwarfs of the spectral class M3.5 and later become fully convective (Chabrier
& Baraffe, 1997). Thus, the conditions for the development of dynamos and
magnetic fields in main-sequence stars are different, and to study the
activity of stars with different parameters, the accumulation of data on
activity indices and magnetic fields remains relevant.

In this paper, we present the results of the search for cycles at four stars –
OU Gem (dK2), EQ Vir (dK5), V1005 Ori (dK0), AU Mic (dM1). These are stars
with fast rotation and magnetic fields of 2–2.6 kG (Shulyak et al., 2017). For
them, the several decade’s photometric series were first obtained and studied,
and possible activity cycles were revealed. The nature of the relationship
between the parameters of the cycle and the average magnetic field for fast-
rotating stars (young age) that have not reached saturation is considered by
the example of the named group of stars, supplemented by several previously
studied objects.

##  2 LONG-TERM LIGHT CURVES AND PHOTOMETRIC DATA SOURCES

The activity cycle associated with the development of sunspots lasts about 11
years. As observations have shown, for solar-type stars and smaller masses,
longer cycles are possible, and therefore, to search for them it is necessary
to study photometric series at intervals of more than 10 years. For the
selected stars long-term light curves were formed according to data obtained
in photographic archives, published results of photoelectric photometry and
taken from the Hipparcos databases, ASAS (Pojmanski, 1997) and KWS
(Kamogata/Kiso/Kyoto Wide-field Survey). In the course of statistical
processing of arrays of $V$-values selected from the indicated databases,
erroneous values and flares were identified and removed, average brightness
values for each observation date, average annual values and errors of their
determination were determined. The mean square errors of $V_{yr}$ – values did
not exceed 0.07m according to photographic data, 0.015m according to
photoelectric data, 0.015m, 0.03m, 0.028m according to Hipparcos, ASAS and
KWS, respectively.

Figure 1:  Changes in the average annual brightness at long-term intervals for
active red dwarfs OU Gem, EQ Vir, V1005 Ori, AU Mic. Different symbols
indicate the following data sources: filled circles – photographic collection
of Sternberg Astronomical Institute, Moscow State University (Bondar’, 1995),
open circles – published photometry data by Cutispoto (1995,1998) and
Cutispoto et al. (2001, 2003), open squares – catalog of Hipparcos satellite
data, open triangles – ASAS photometric catalog, filled squares – KWS
database. The dashed line marks the level of maximum brightness on the
presented observational interval.

For the star OU Gem it were used photographic magnitudes for 1899–1988
(Bondar’, 1995), electrophotometry collected by Alekseev (2001) obtaining from
his observations at the 1.25 m AZT-11 telescope and taken from publications
(1972–1988), and results from databases Hipparcos (1990–1992), ASAS
(2000–2009) and KWS (2010–2019). The $B$-magnitudes added from photographic
data were converted to $V$-values according to the corresponded $B-V$-values.

The complete light curve in Fig. 1 covers the time interval of 120 years, from
1899 to 2019, the number of average annual $V$-values $N=56$. The brightness
changes from year to year amounted to 0.2m; the maximum level (marked by a
dashed line) was reached in 1962 and 1964 (Argue, 1963) and 2004 (ASAS).

The behavior of the average annual brightness of EQ Vir is presented on the
interval 1989–2019 ($N=25$) by photometry from the Hipparcos (1989–1993), ASAS
(2000–2009) and KWS databases (2010–2019) (Fig. 1). Changes in the brightness
amounted of 0.22m. The photographic data for 1914–1988 (Bondar’, 1995) are not
numerous and very sparsed, they were not included in the data array for a
search for the cycle, but we took into account, that on this interval and also
in 1993–1998 (Alekseev, 2001), the brightness did not reach its maximum of
$V=9.20^{m}$ that was found from ASAS and KWS data.

For star V1005 Ori, the results of 1974–1976 obtained by Bopp and Espenak
(1977), Bopp et al. (1978), data for 1980–1981 by Byrne et al. (1984) and
1992–1999 (Alekseev, 2001) were taken, and $V$-values from Hipparcos
(1990–1993), ASAS (2001–2009) and KWS (2010–2019) as well. The average annual
values from the Hipparcos catalog were recalculated, $V_{yr}=V_{Hip}-0.11$
correspondently to the data from (Alekseev, 2001). The light curve in Fig. 1
includes 34 epochs of observations. Changes in the average annual brightness
from 1974 to 2019 amounted to 0.19m, on the entire studied interval the
maximum brightness level of 9.25m was observed only once, in 1994.

The AU Mic light curve (Fig. 1) covers the interval from 1972 to 2018. The
yearly mean values ($N=32$) were obtained from data by Cutispoto (1995; 1998),
Cutispoto et al. (2001; 2003) Hipparcos (1990–1992), ASAS (2001–2009) and KWS
(2013–2018). Changes in the average annual brightness were 0.27m, and the
maximum brightness was 8.59m in 2000. According to archival data from Phillips
and Hartmann (1978), this level was not reached on the span from 1913 to 1971.
In Table 1, we present the maximum magnitudes of stars obtained by us in the
studied time interval and the data from the SIMBAD.

Table 1:  Maximal $V$-magnitudes for investigated stars  star name | time |  $V$, mag |  $V_{max}$, mag | years of maximum
---|---|---|---|---
| interval | (SIMBAD) |  | in $V_{yr}$-values
OU Gem | 1899–2019 | — | 6.74 | 1962, 2007
EQ Vir | 1989–2019 | 9.37 | 9.20 | 2000, 2015
V1005 Ori | 1974–2018 | 10.11 | 9.95 | 1994
AU Mic | 1972–2018 | 8.63 | 8.59 | 2000

##  3 SEARCH FOR POSSIBLE CYCLES IN PHOTOSPHERES OF THE SELECTED STARS

Long-term light curves make it possible to determine the epochs of maximum
brightness and the amplitude of variability. Changes in the average annual
brightness for active solar-type stars and red dwarfs are explained in the
frameworks of the concept of the development of surface starspots. The epochs
of minimum brightness correspond to the maximum spottedness (maximum
activity), and spots on the surface of the star are absent or their number is
minimal in the years of the greatest brightness. The interval between
successive epochs of the star’s maximum brightness (activity minima) shows the
duration of the possible cycle of its photospheric activity. The stellar
activity cycle can last several decades and, according to available
observations, it is rarely possible to trace the development of several
cycles. Therefore, the found long-term cycles should now be considered
possible or suspected, but their search allows us to identify stars with
cycles and irregular activity, which is important for studying the nature of
the magnetic activity of stars.

The search for periods in brightness variations for the stars considered by us
was performed used the methods of Yurkevich and Hartley as described early by
Bondar’ (2019). For OU Gem, for a number of average annual $V$-values, the
presence of periods of less than 60 years was considered; the best data
convolution was obtained for a period of 41.6 years. Figure 3 shows the phase
curve for this period and the approximation of the average annual values in
bins of 0.1 phases by a 5th degree polynomial (dashed line), the initial epoch
is chosen arbitrarily, $T_{0}$ = 1899. The amplitude of the possible cycle is
0.09m.

Figure 2:  Activity cycle in photosphere of EQ Vir from $V$-data obtained in
1989–2019. a) Average $V$-values for the date of observations according to the
data from Hipparcos, ASAS and KWS, description to symbols as in Fig. 1. b) The
convolution of the averaged $V$-data with $T_{0}(JD)=2447868$ and the found
cycle of 6059.53 d shows two consecutive cycles marked with dots and crosses.

For EQ Vir, we analyzed a series of averaged $V$-magnitudes for each date of
observations (Fig. 2). According to the ASAS and KWS data, the possible cycle
($P_{cyc}$) on the interval JD2451900–2458569 was determined as equals to
6095.62 days. The Hipparcos data are corresponded to the convolution with this
period, and we have precised the value of the possible cycle for the entire
data on the interval JD 2447868–2458569 ($T_{0}=2447868.49$, $N=874$). With
the obtained $P_{cyc}=6059.53\;$days (16.59 years), two waves of this cycle
were observed. They are shown by the corresponding icons in the left graph of
Fig. 2. It can be seen that the shape and phase of the cycle are not changed.
A convolution of the mean yearly $V$-values is shown in Fig. 3, $T_{0}=1989$,
the approximation by bins equal to 0.1 of the phase represents the shape of
the found cycle and its amplitude $A_{cyc}=0.19^{m}$.

Figure 3:  Long-term activity cycles in the studied stars. Filled circles
present average annual $V$-values, dashed lines draw an approximation of phase
curves by a high order polynomial and show the shape and amplitude of a
possible cycle.

For the M-dwarfs V1005 Ori and AU Mic, the search for possible periods is
complicated by the fact that only one epoch of maximum brightness was recorded
on the studied intervals for these stars. Periodogram analysis was performed
for a series of average annual $V$-values and for the row obtained by
approximating the light curve with a high degree polynomial. The best
convolution of the yearly mean $V$-values was obtained for V1005 Ori with the
period of 38.06 years ($T_{0}=1974$), for AU Mic – with a period of 40.6 years
($T_{0}=1972$) (Fig. 3). The amplitude of the suspected cycles is 0.13m and
0.21m, respectively. Approximation by polynomials has been carried out
according to the average values in bins equal to 0.1 of the phase of the
accepted periods. The parameters of the discussed activity cycles are shown in
Table 2.

Table 2:  Parameters of photospheric activity cycles and magnetic fields for
the researched red dwarfs

star name | spectral type | $B-V$ | $P_{cyc},y$ |  $A_{cyc}$, mag | ref |  $\langle B\rangle$, G | ref
---|---|---|---|---|---|---|---
LQ Hya | K2.0 | 0.91 | 18 | 0.27 | 6 | 2450 | 1
OU Gem | K2.0 | 0.95 | 41.6 | 0.09 | 9 | 2400 | 2
EQ Vir | K5.0 | 1.18 | 16.6 | 0.19 | 9 | 2000 | 3
V833 Tau | K5.0 | 1.04 | 78 | 0.6 | 7 | 1400 | 1
V1005Ori | M0.0 | 1.37 | 38.1 | 0.13 | 9 | 2600 | 4
AU Mic | M1.0 | 1.32 | 40.6 | 0.21 | 9 | 2300 | 5
DT Vir | M2.0 | 1.47 | 31.45 | 0.15 | 8 | 2600 | 4
AD Leo | M3.5 | 1.55 | 27 | 0.16 | 6 | 3100 | 4
DX Cnc | M6.5 | 2.05 | 2.67 | 0.10 | 8 | 3200 | 4

References: (1) Saar S. H., 1996; (2) Saar & Linsky, 1986; (3) Saar S. H. et
al. 1986; (4) Shulyak et al., 2017; (5) Saar S. H., 1994; (6) Alekseev &
Kozhevnikova 2017; (7) Bondar’ 2015; (8) Bondar’ 2019; (9) this paper

##  4 ACTIVITY CYCLES AND MAGNETIC FIELDS

The spots on star’s surface are regions of an enhanced magnetic field, and
therefore, the surface magnetic field of active stars is inhomogeneous. In
this case, the average magnetic field is calculated as the sum of the weighted
values of the magnetic field strength $\langle B\rangle=\Sigma|B_{i}|f_{i}$ in
each of its elements with the coefficient $f_{i}$, the filling-factor, which
expresses the area of the region covered by the magnetic field with the
intensity $|B|_{i}$ in fractions of stellar surface area (Shulyak et al.,
2014; 2017). In these works, the authors give a method for determining the
average surface magnetic field on low-mass stars.

The G–M dwarfs studied by us were selected from the list of stars with
measured magnetic fields (Shulyak et al., 2017). According to the data in the
list, the average magnetic field is amplified in rapidly rotating fully
convective M stars, for some of them $\langle B\rangle$ exceeds 4 kG. We tried
to consider the effect of a surface magnetic field on the development of
cyclic photospheric activity according to photometric observations. As is
known, the amplitude of the cycle is related to the area occupied by the
spots: $A^{2}_{cyc}\sim S_{spot}$. To consider the relationship between cycle
parameters and $\langle B\rangle$, we added in our sample 5 K–M dwarfs,
parameters of their cycles were taken from (Bondar’, 2019). The list of stars,
parameters of cycles and the mean magnetic fields are presented in Table 2.

Figure 4:  The relationship between the surface magnetic field and the
activity cycle parameters of fast-rotating red dwarfs.

Besides V833 Tau, the averaged surface magnetic fields of the considered stars
are 2–4 kG. For stars with such fields, the amplitude and duration of the
cycle are increased with a decreasing of $\langle B\rangle$ that is displayed
on Fig. 4. The limited number of the considered stars allows us only to
propose the observed tendency. The deviations from the regression line that
are noticeable in the graphs, as well as deviations of the cycle parameters
for V833 Tau, can be caused both by errors in their determination and the
actual existence of groups of stars with a specific type of relationship
between the magnetic field and parameters of cycles. The question of whether
it is possible to expect the development of long and high-amplitude cycles on
stars with surface magnetic fields $<2\;$kG requires further study.

##  5 CONCLUSION

The behavior of the average annual brightness of two K-dwarfs OU Gem and EQ
Vir and the early M-dwarfs V1005 Ori and AU Mic was first studied on time span
covers of several decades using photometry from databases for 1989–2019. Long-
term series allowed us to determine maximum brightness values for the studied
stars, all of them differ from those given in the astronomical SIMBAD
database. The variability of the average annual brightness of all stars is
cyclical.

The durations of possible cycles for OU Gem, V1005 Ori and AU Mic are 40–42
years, for EQ Vir – 16.6 years, and amplitudes are not more than 0.2m.
Measurements of the magnetic fields of the stars studied by us showed that the
average surface magnetic field strengths are several kilogauss. We examined
the nature of the relationship between the parameters of the cycle, its
duration and amplitude, and the value of $\langle B\rangle$, including another
5 stars with strong magnetic fields.

A noticeable tendency is an increase of the amplitude and duration of a cycle
with a decrease in the value of $\langle B\rangle$. This may be due to the
fact that with an increase in the surface magnetic field, it becomes more
uniform and the level of activity changes to a lesser extent than in stars
with strong local fields concentrated in large spots. It is known that the
surface of M-dwarfs is covered with small but numerous spots.

## ACKNOWLEDGMENTS

The authors are grateful to A.A. Shlyapnikov for help in working with
databases, also to Z.A. Taloverova for technical help in preparation of text.
In the work we used information from the SIMBAD database, photometric data
from the Hipparcos, the International Variable Star Index (VSX) database, the
Kamogata-Kiso-Kyoto Wide-Field Survey. The authors are thankful to all the
staff providing the replenishment of these databases and access to them, as
well as the developers of the AVE software package.

## FUNDING

This work was carried out with the partial support of the Russian Foundation
for Basic Research (grant 19-02- 00191a and 18-52-06002 Az_a).

## CONFLICT OF INTEREST

The authors declare that they have no conflicts of interest.

## References

  * [1] Alekseev I.Yu. Zapyatnennye zvezdy malych mass. Odessa: Astroprint, 137 pp. 2001. (rus.)
  * [2] Alekseev I.Yu., Kozhevnikova A.V. Long-term variations in the spottedness of BY Dra M dwarfs // Astron. Rep. V.61. No.3. P.221-232. 2017.
  * [3] Alekseev I.Yu., Bondar’ N.I. Spottedness of the emission-line dwarf stars BF CVn, DT Vir, EQ Vir, and V1396 Cyg from photoelectric and photographic observations //Astron. Let. V.23. No.2. P.257-262. 1997.
  * [4] Argue A.N. UBV photometry of 300 G and K type stars // MNRAS. V.125. P.557-570. 1963.
  * [5] Baliunas S.L., Nesme-Ribes E., Sokoloff D., Soon W.H. A dynamo interpretation of stellar activity cycles // Astrophys. J. V.460. P.848-854. 1996.
  * [6] Bondar’ N.I. The long-term variability in active red dwarfs // Astron. Astrophys. Suppl. Ser. V.111. No.2. P.259-264. 1995.
  * [7] Bondar’ N.I. The activity cycle of V833 Tau from photometric data for 1899-2009 // Astron. Rep. V.59. No.3. P.221-227. 2015.
  * [8] Bondar’ N.I. Time-scales of activity cycles in solar-type stars and K-M dwarfs // Astron. Astrophys. Trans. V.31. No.3. P.295-302. 2019.
  * [9] Bopp B.W., Espenak F. Survey of the BY Draconis syndrome among dMe stars // Astron. J. V.82. P.916-924. 1977.
  * [10] Bopp B.W., Torres C.A., Busko I.C., Qust G.R. Observations of the BY Draconis Variable Gliese 182 // IBVS. No.1443. P.1. 1978.
  * [11] Byrne P.B., Doyle J.G., Butler C.J. Optical photometry and ultraviolet spectroscopy of the flare BY DRA star GL 182(V 1005 Ori) // MNRAS. V.206. P.907-918. 1984.
  * [12] Chabrier G., Baraffe I. Structure and evolution of low-mass stars // A&A. V.327. P.1039-1053. 1997\.
  * [13] Cutispoto G. Long-term monitoring of active stars. IV. UBV(RI)_c_ observations obtained at La Silla in December 1989 // Astron. Astrophys. Suppl. Ser. V.111. P.507. 1995.
  * [14] Cutispoto G. Long-term monitoring of active stars. VII. UBV(RI)_c photometry collected in March 1991 // Astron. Astrophys. Suppl. Ser. V.127. P.207-215. 1998.
  * [15] Cutispoto G., Messina S., Rodonò M. Long-term monitoring of active stars. IX. Photometry collected in 1993 // A&A. V.367. P.910-930. 2001.
  * [16] Cutispoto G., Messina S., Rodonò M. Long-term monitoring of active stars. X. Photometry collected in 1994 // A&A. V.400. P.659-670. 2003.
  * [17] Distefano E., Lanza A. C., Lanza A. F., Messina S., Spada F. Activity cycles in members of young loose stellar associations // A&A. V.606. A58. 14 pp. 2017.
  * [18] Ibañez Bustos R.V., Buccino A.P., Flores M., Martínez C. I., Maizel D., Messina S., Mauas P. J. D. First long-term activity study of AU Microscopii: a possible chromospheric cycle // MNRAS. V.483. P.1159-1167. 2019.
  * [19] Oláh K., Kővári Zs., Petrovay K., Soon W., Baliunas S., Kolláth Z., Vida K. Magnetic cycles at different ages of stars // A&A. V. 590. id.A133. 13 pp. 2016.
  * [20] Phillips M.J., Hartmann L. Long-term variability of dMe stars // Astrophys. J. V.224. P.182-184. 1978.
  * [21] Pojmanski G. The all sky automated survey // Acta Astron. V.47. P.467-481. 1997.
  * [22] Reiners A., Basri G., Browning M. Evidence for Magnetic Flux Saturation in Rapidly Rotating M Stars // Astrophys. J. V.692. P.538-545. 2009.
  * [23] Saar S.H., Linsky J.L. New measurements of photospheric magnetic fields in late-type stars and emerging trends //Adv.Space Phys. V. 6. No.8. P.235-238. 1986.
  * [24] Saar S. H., Linsky J. L., Beckers J. M. The Magnetic Field of the BY Draconis Flare Star EQ Virginis // ApJ. V.302. P.777-784. 1986.
  * [25] Saar S. H. New Infrared Measurements of Magnetic Fields on Cool Stars // in: IAU Symposium V.154. Infrared Solar Physics / Eds. Rabin D. M., Jefferies J. T., Lindsey C. P.493-497. 1994\.
  * [26] Saar S. H. Recent magnetic fields measurements of stellar magnetic fields // in: IAU Symposium V.176. Stellar Surface Structure / Eds. Strassmeier K. G., Linsky J. L. P. 237-244. 1996.
  * [27] Savanov I.S. Activity cycles of M dwarfs // Astron. Rep. V.56. P.716-721. 2012.
  * [28] Suárez Mascareño A., Rebolo R., González Hernández J.I. Magnetic cycles and rotation periods of late-type stars from photometric time series // A&A. V.595. A12. 14 pp. 2016.
  * [29] Shulyak D., Reiners A., Seemann U., Kochukhov O., Piskunov N. Exploring the magnetic field complexity in M dwarfs at the boundary to full convection // A&A. V.563. A35. 15 pp. 2014.
  * [30] Shulyak D., Reiners A., Engeln A., Malo L., Yadav R., Morin J., Kochukhov O. // Nature Astronomy. V.1. id.0184. 2017.
  * [31] Shulyak D., Reiners A., Nagel E., et al. Magnetic fields in M dwarfs from the CARMENES survey // A&A. V.626. id.A86. 24 pp. 2019.