Munarini graphs: a generalization of Fibonacci cubes and Pell graphs. Part I
Michel Mollard · 2026
Read Munarini graphs: a generalization of Fibonacci cubes and Pell graphs. Part I by Michel Mollard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14613.txt.
Introduction
Mollard introduces Munarini graphs. They offer a new take on Fibonacci cubes and Pell graphs. Fibonacci cubes take hypercube vertices with no consecutive ones. Pell graphs vary them on ternary strings. Munarini graphs extend both. Unlike a rival generalisation, they are daisy cubes, as Fibonacci cubes and Pell graphs are. This first part studies their size, recursive build, and cube polynomials.
Catalog record
| CREATOR | Michel Mollard |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47896 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14613
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Munarini graphs: a generalization of Fibonacci cubes and Pell graphs. Part I Michel Mollard Abstract The Fibonacci cube Γ n \Gamma_{n} is the subgraph of the hypercube Q n Q_{n} induced by vertices with no consecutive 1 1 s. Munarini introduced Pell graphs, a variation of Fibonacci cubes defined on ternary strings. A generalization of Pell graphs to ( k + 1 ) (k+1) -ary strings has recently been proposed. In this paper we introduce Munarini graphs, which constitute an alternative generalization of Fibonacci cubes and Pell graphs. One of the main advantages of Munarini graphs is that, unlike previously proposed generalization, they are daisy cubes, as are Fibonacci cubes and Pell graphs. In this first article, we study some of their fundamental properties including the size, the recursive structure, the cube and maximal cube polynomials. Keywords: Hypercube, Fibonacci cube, Pell graphs, Daisy cubes. AMS Subj. Class. : 05C07,05C35 1 Introduction This work is dedicated to Emanuele Munarini, who passed away in 2024. Emanuele introduced Pell graphs [ 20 ] and was also a co-author of the seminal paper on the structural and enumerative properties of Fibonacci cubes [ 19 ] . It is therefore natural to name the generalization of these graphs introduced here after him. Fibonacci strings are binary strings with no consecutive 1 s. The Fibonacci cube of dimension n , denoted \Gamma_{n} , is the subgraph of the hypercube Q_{n} induced by Fibonacci strings of length n . Fibonacci cubes were introduced in 1993 by W.-J. Hsu as a model for interconnection networks [ 7 ] . Since then, they have found numerous applications and have also proved to be of independent combinatorial interest. In 2013, a review article on Fibonacci cubes was written by Sandi Klavžar [ 13 ] and recently a full book about them has been published [ 3 ] . The investigation of the properties of Fibonacci cubes has attracted many researchers and led to the development of a variety of interesting generalizations and variations, which are covered in an entire chapter of the book [ 3 ] . Among these families of graphs are Lucas cubes, generalized Fibonacci cubes, Pell graphs, k -Fibonacci cubes, Fibonacci p -cubes and Fibonacci-run graphs. The structure of Fibonacci cubes is closely related to the Fibonacci numbers: F_{0}=0 , F_{1}=1 , F_{n}=F_{n-1}+F_{n-2} for n\geq 2 . One of the generalizations of them is the k -Fibonacci sequence defined for a positive integer k as F_{n,k}=kF_{n-1,k}+F_{n-2,k} for n\geq 2 with initial values F_{0,k}=0 and F_{1,k}=1 . The 1 -Fibonacci sequence is thus the Fibonacci sequence. If k=2 , we obtain another famous sequence, that of Pell numbers P_{n} , where P_{0}=0 , P_{1}=1 , P_{n}=2P_{n-1}+P_{n-2} for n\geq 2 . Motivated by the Pell sequence, Emanuele Munarini [ 20 ] introduced the Pell graph \Pi_{n} , defined on Pell strings, a subset of the set of strings of length n over the alphabet {0,1,2}. The structure of \Pi_{n} reflects the recurrence P_{n}=2P_{n-1}+P_{n-2} . Fibonacci cubes and Pell graphs [ 3 , Theorem 9.68] belong to the class of daisy cubes [ 10 ] , a family of isometric subgraphs of hypercubes. Recently, inspired by the k -Fibonacci numbers for k\geq 2 , a generalization of Pell graphs, the generalized Pell graphs \Pi_{n,k} , have been proposed by Vesna Iršič, Sandi Klavžar and Elif Tan [ 8 ] . Note that \Pi_{n,k} is not a daisy cube for k\geq 3 and n\geq 3 . Also inspired by k -Fibonacci numbers, Tomislav Došlič and Luka Podrug [ 2 ] studied a second family of graphs, the metallic cubes \Pi_{n}^{k} , having the same order and size as \Pi_{n,k} . However, they do not constitute a generalization of Pell graphs because \Pi_{n}^{2} is not isomorphic to the Pell graph \Pi_{n} for n\geq 3 . Furthermore metallic cubes are not daisy cubes either. In this article, we introduce a family of graphs that we call Munarini graphs M_{n,k} . These graphs have the same order and size as generalized Pell graphs, but, unlike them, they are daisy cubes. The inductive structure of Munarini graphs is another interpretation of the recurrence relation F_{n,k}=kF_{n-1,k}+F_{n-2,k} . Indeed, M_{n,k} is constructed from M_{n-2,k} and k copies of M_{n-1,k} connected along the star S_{k-1} , whereas in \Pi_{n,k} and \Pi_{n}^{k} , the k subgraphs of dimension n-1 form a path P_{k} (see Figure 2 ). Furthermore Munarini graphs generalize both Fibonacci cubes and Pell graphs since M_{n,1}\cong\Gamma_{n-1} and M_{n,2}\cong\Pi_{n} . We will study the fundamental properties of Munarini graphs and show that several of their enumerative properties yield formulas very close to those of Fibonacci cubes and Pell graphs. This paper is organized as follows. In the next section we formally define the concepts used in this paper and fix some notations. We then introduce Munarini graphs M_{n,k} and determine their first properties, such as the number of edges and the recursive structure. In Section 3 we study M_{n,k} as subgraphs of hypercubes and Fibonacci cubes. In Section 4 we determine the cube polynomial and study hypercubes and maximal hypercubes in M_{n,k} . 2 Preliminaries We now introduce the concepts and notations needed in this paper. Throughout this article, we use the dotted union symbols A\dot{\cup}B or \dot{\bigcup}_{k\geq 0}{A_{k}} to enphasize that the sets are disjoint. Let k\geq 1 . A (k+1) -ary string s of length l(s) , string for short, is a sequence of l(s) characters in \{0,1,\ldots k\} . Let i\in\{0,1,\ldots k\} , then |s|_{i} is the number of occurrences of i in s . An alphabet is a set of symbols classically called letters; in our context, these letters may themselves be (k+1) -ary strings. For example \Sigma=\{0,1,2\} or \Sigma=\{0,1,22\} are alphabets over ternary strings. Let {\mathcal{A}} be the set of words generated freely (as a monoid) by the alphabet \Sigma . This means that words s\in{\mathcal{A}} can be written uniquely as a concatenation of zero or more letters from \Sigma . For example, for \Sigma=\{0,1,22\} , the string 0221 belongs to {\mathcal{A}} , but 02221 does not. Note that the empty string \lambda always belongs to {\mathcal{A}} . Let s be a (k+1) -ary string and a\in\{0,\ldots,k\} , then a run of a s in s is a maximal substring of s consisting entirely of the character a . For a set of strings {\mathcal{B}} and a string s we denote by s{\mathcal{B}} (respectively {\mathcal{B}}s ) the sets of strings obtained by concatenation of s with a string in {\mathcal{B}} (respectively a string in {\mathcal{B}} with s ). Let us consider the special case of binary strings so k=1 , and let B=\{0,1\} . It will be convenient to identify elements u=(u_{1},\ldots,u_{n})\in B^{n} and strings of length n over B . We thus briefly write u as u_{1}\ldots u_{n} and call u_{i} the i -th coordinate of u . For j\in\{1,\ldots,n\} the string u+\delta_{j} is defined as the string v such that v_{j}\neq u_{j} and v_{i}=u_{i} for all i\neq j . We use the power notation for concatenation of bits, for instance 0^{n}=0\ldots 0\in B^{n} . The Hamming distance between two strings in B^{n} is the number of coordinates the strings differ. The vertex set of Q_{n} , the hypercube of dimension