A Family of Partial Cubes with Minimal Fibonacci Dimension

Let $G=(V(G),E(G))$ be a graph. The distance of two nodes $u,v\in V(G)$, denoted by ${\mathrm{dist}}_G(u,v)$, is the length of the shortest path connecting $u$ and $v$ in $G$. A subgraph $G^{\prime }$ of a (connected) graph $G$ is an isometric subgraph of $G$ if for any $u,v\in V(G^{\prime })$, ${\mathrm{dist}}_{G^{\prime }}(u,v)={\mathrm{dist}}_G(u,v)$.

Let $G,G^{\prime }$ two graphs. An isometric embedding $\beta$ of $G^{\prime }$ in $G$ is a map $\beta :V(G^{\prime })\to V(G)$ which preserves distances, i.e., for any $u,v\in V(G^{\prime })$, ${\mathrm{dist}}_{G^{\prime }}(u,v)={\mathrm{dist}}_G(\beta (u),\beta (v))$. If an isometric embedding $\beta$ of $G^{\prime }$ in $G$ does exist, then we say that $G^{\prime }$ can be isometrically embedded into $G$ and write $G^{\prime }{⊴}_{\beta }G$. The symbol $⊴$ is used to indicate that an isometric embedding does exist.

Recall that, given two binary strings $x$ and $y$, their Hamming distance, $dis{t}_H(x,y)$ is the number of positions at which $x$ and $y$ differ.

The $k$-hypercube, or binary $k$-cube, $Q_k$, is a graph with $2^k$ vertices, each associated to a binary word of length $k$, called its label. The label map, denoted by ${\lambda }_k$, of the $k$-hypercube $Q_k$ is based on the Hamming distance, i.e., it is such that two vertices $u$ and $v$ are adjacent if and only if ${\mathrm{dist}}_H({\lambda }_k(u),{\lambda }_k(v))=1$. This implies that the distance between any two vertices $u$ and $v$ is simply given by the Hamming distances between the corresponding labels, i.e. ${\mathrm{dist}}_{Q_k}(u,v)={\mathrm{dist}}_H({\lambda }_k(u),{\lambda }_k(v))$.

A graph $G$ is a partial cube if $G$ can be isometrically embedded into a hypercube $Q_k$, for some $k$. The relevant fact is that such isometric embedding makes $G$ inherit from $Q_k$ a labeling of its vertices by strings in ${\mathrm{\Sigma }}^k$ that makes the distance of the vertices in $G$ equal to the Hamming distance between their corresponding labels. Note that all the isometric subgraphs of the hypercubes are partial cubes by definition.

The Fibonacci cube ${\mathrm{\Gamma }}_k$ of order $k$ is the subgraph of $Q_k$ whose vertices are all binary words that do not contain the factor $11$. It is well known that ${\mathrm{\Gamma }}_k$ is an isometric subgraph of $Q_k$ (cf. [27]). Therefore, the Fibonacci cubes are partial cubes.

Let $\mathrm{\Sigma }$ be a finite alphabet. In this paper, the alphabet is $\mathrm{\Sigma }=\{0,1\}$, although many of the definitions and results can be stated and hold for a general alphabet. If $a\in \mathrm{\Sigma }$, $\overline{a}$ denotes the opposite of $a$, i.e. $\overline{a}=1$ if $a=0$ and vice versa. A word (or string) $w$ of length $|w|=n$ is $w=a_1{a}_2\mathrm{\cdots }{a}_n$, where $a_1,a_2,\mathrm{\dots },a_n$ are symbols in $\mathrm{\Sigma }$. Then, $\overline{w}={\overline{a}}_1{\overline{a}}_2\mathrm{\dots }{\overline{a}}_n$ is the complement of $w$, and $w^R=a_n{a}_{n-1}\mathrm{\dots }{a}_1$ is the mirror of $w$. The set of all finite words over $\mathrm{\Sigma }$ is denoted ${\mathrm{\Sigma }}^{\ast }$ and the set of all words over $\mathrm{\Sigma }$ of length $n$ is denoted ${\mathrm{\Sigma }}^n$.

Let $w[i]$ denote the symbol of $w$ in position $i$, i.e., $w[i]=a_i$. Then, $w[i..j]=a_i\mathrm{\cdots }{a}_j$, for $1\le i\le j\le n$, is a factor of $w$ that occurs in the interval $[i..j]$. The prefix (resp. suffix) of $w$ of length $\mathrm{\ell }$, with $1\le \mathrm{\ell }\le n-1$ is ${\mathrm{pre}}_{\mathrm{\ell }}(w)=w[1..\mathrm{\ell }]$ (resp. ${\mathrm{suf}}_{\mathrm{\ell }}(w)=w[n-\mathrm{\ell }+1..n]$). When ${\mathrm{pre}}_{\mathrm{\ell }}(w)={\mathrm{suf}}_{\mathrm{\ell }}(w)=u$ then $u$ is an overlap of $w$ of length $\mathrm{\ell }$.

In the sequel, the notion of overlap with errors is also needed. A word $w$ has a $2$-error overlap ($2$-eo, for short) of length $\mathrm{\ell }$ if ${\mathrm{pre}}_{\mathrm{\ell }}(w)$ and ${\mathrm{suf}}_{\mathrm{\ell }}(w)$ differ in two positions, namely, they have a Hamming distance equal to $2$; the two positions are called error positions. We say that $w$ has a $2$-error overlap if $w$ has a $2$-eo of length $\mathrm{\ell }$ for some $1\le \mathrm{\ell }\le n-1$.

Given two words $w,f\in {\mathrm{\Sigma }}^{\ast }$, $w$ is $f$-free if $w$ does not contain $f$ as a factor; we also say that $w$ avoids $f$.

We now shortly report some recent results on isometric words (originally called good words) that are used to define special isometric subgraphs of the hypercubes (cf. [26, 28, 29, 32]).

Let $u,v\in {\mathrm{\Sigma }}^{\ast }$ be words of equal length and ${\mathrm{dist}}_H(u,v)=d$. A transformation $\tau$ from $u$ to $v$ is a sequence of $d+1$ words $(w_0,w_1,\mathrm{\dots },w_d)$ such that $w_0=u$, $w_d=v$, and for any $k=0,1,\mathrm{\dots },d-1$, ${\mathrm{dist}}_H(w_k,w_{k+1})=1$. Moreover, $\tau$ is $f$-free if for any $i=0,1,\mathrm{\dots },d$, the word $w_i$ is $f$-free. This is the base for the following definition.

A pair of $f$-free words $(u,v)$ such that any transformation from $u$ to $v$ is not $f$-free proves that $f$ is non-isometric and is called a pair of witnesses for $f$; the positions where $u$ and $v$ differ are called error positions. The minimal length of a word $u$ in a pair of witnesses for $f$ is called the index of $f$, and denoted by $i(f)$.

Coming back to graphs and hypercubes we recall the following definition of Generalized Fibonacci cubes, or hypercubes avoiding a word, first introduced in [25].

Note that, using this definition, the Fibonacci cube ${\mathrm{\Gamma }}_k$ coincides with $Q_k(11)$. Moreover, we assume implicitly that $Q_k(f)$ is still a labeled graph keeping the original labels of the hypercube $Q_k$ from which it is derived.

Then, one immediately realizes the strict connection between isometric subgraphs of $Q_k$ of type $Q_k(f)$ and isometric words. It holds that $Q_k(f)$ is an isometric subgraph of $Q_k$ if and only if $f$ is isometric. Moreover, in [34], it is proved the non-obvious result that if $f$ is not isometric then for all $k\ge i(f)$, $Q_k(f)$ is not even a partial cube, i.e., $Q_k(f)$ does not isometrically embed into any $Q_{k^{\prime }}$ with $k^{\prime }\ge i(f)$. These considerations lead to the following proposition.

Furthermore, note that if $f$ is a non-isometric word and $i(f)$ is its index, then for any , $Q_k(f)⊴Q_k$, while for any $k\ge i(f)$, $Q_k(f)\mathrm{／}⊴Q_k$. Finally, remark that if $f$ is isometric, also its complement $\overline{f}$ and its mirror $f^R$ are isometric. Consequently, also the graphs $Q_k(\overline{f})$ and $Q_k(f^R)$ (that can be also obtained from $Q_k(f)$ by, respectively, complementing or reversing all the labels) are isometric subgraphs of $Q_k$.

A further step in the generalization of Fibonacci cubes is done in [3] by introducing the notion of isometric set of words. In what follows, $S$ denotes a finite subset of ${\mathrm{\Sigma }}^{\ast }$. Then a word $w$ is $S$-free, if $w$ does not contain any word in $S$ as a factor.

A set $S$ is non-isometric if it is not isometric. If $S$ is non-isometric, a pair of witnesses for $S$ is a pair $(u,v)$ with $|u|=|v|\ge \max$, such that each transformation from $u$ to $v$ contains a word that is not $S$-free.

Examples of isometric sets (cf. [3], [19]) are the sets $D_h=\{11,101,\mathrm{\dots }{10}^{h}1\}$, for any $h\ge 0$. Note that $D_0=\{11\}$. As in the case of a single word (cf. [29] and [28]), it can be shown that the non-isometricity of a set $S$ is again connected to some properties on overlaps defined on a pair of (possible) different words in $S$.

Note that the existence of a $2$-eo of $f$ on $g$ does not imply the existence of a $2$-eo of $g$ on $f$. In particular, if $g=f$ Definition 5 coincides with the classical definition of $2$-eo of a word (cf. [29]).

The following proposition, given in [29], characterizes isometric words.

The proof of Proposition 7 is constructive. In fact, if $f$ has a $2$-error overlap of shift $r$, then the proof explicitly provides a “standard” pair of witnesses for $f$. The pair is defined as $({\alpha }_r(f),{\beta }_r(f))$ or $({\eta }_r(f),{\gamma }_r(f))$, in the case that ${\beta }_r(f)$ is not $f$-free. More exactly, it turns out that ${\beta }_r(f)$ is not $f$-free if and only if the $2$-error overlap of $f$ satisfies the so-called $Conditio{n}^{\ast }$ (cf. [29]). Moreover, in [9], it is shown that this construction yields the pairs of witnesses of minimal distance and length. Let us recall the construction (see Fig. 1 for $({\alpha }_r(f),{\beta }_r(f))$).

The following theorem generalizes to any set $S\subseteq {\mathrm{\Sigma }}^{\ast }$ an analogous result for sets of words of equal length in [3]. Its proof rephrases the other one and is here sketched for the sake of completeness.

In this last part of the section, we report some results from Cabello et al. [14] where Fibonacci dimension of a graph is first introduced and investigated. The isometric dimension of a graph $G$, denoted by $idim(G)$, is the smallest integer $k$ such that $G$ admits an isometric embedding into $Q_k$. If no such $k$ exists, $idim(G)=\mathrm{\infty }$. Therefore $idim(G)$ is finite if and only if $G$ is a partial cube.

Let $\beta :V(G)\to V(Q_k)$ be an isometric embedding of a graph $G$ into the hypercube $Q_k$. The embedding $\beta$ is redundant if there exists $i\in \{1,2,\mathrm{\dots },k\}$ such that the labels of all vertices in $\beta (V(G))$ have the same $i$-th coordinate. It is irredundant otherwise. If an embedding is redundant, another embedding can be found into a lower-dimensional hypercube by omitting the redundant coordinate.

Let us recall the following result that will be largely used in the sequel.

The authors then introduce the Fibonacci dimension of a graph $G$, $fdim(G)$, as the smallest integer $d$ such that $G$ admits an isometric embedding into the Fibonacci cube ${\mathrm{\Gamma }}_d$, and set $fdim(G)=\mathrm{\infty }$ if there is no such $d$. This is strictly related to the isometric dimension since it is shown that a graph isometrically embeds in some hypercube $Q_k$ iff it isometrically embeds in some Fibonacci cube ${\mathrm{\Gamma }}_d$. Note that in general $d\ge k$. They established upper and lower bounds as stated in the following proposition.

In [14], graphs $G$ with maximal Fibonacci dimension $2idim(G)-1$ have been fully characterized. While the algorithm to compute the isometric dimension of a graph is quadratic (cf. [23]), it is proved, instead, that deciding for a given graph $G$ whether or not $idim(G)=fdim(G)$ is an NP-hard problem. In general, it is difficult to find graphs with “small” Fibonacci dimension. An important family of graphs with this property is the set of trees, for which they prove the following result.

Note that trees are very special partial cubes since they have the maximal possible isometric dimension, namely equal to the number of edges. This property derives from the acyclicity and it is the one exploited to compute the Fibonacci dimension.