穆纳里尼图：斐波那契立方体与佩尔图的推广，第一部分

《Discrete Applied Mathematics》：Munarini graphs: A generalization of Fibonacci cubes and Pell graphs, Part I

　　

## 摘要

斐波那契立方体Γn是由超立方体Qn中没有连续1的顶点所诱导的子图。Munarini引入了Pell图，这是在三元字符串上定义的斐波那契立方体的一种变体。最近提出了一种将Pell图推广到(k+1)-元字符串的泛化方法。在本文中，我们引入了Munarini图，它构成了斐波那契立方体和Pell图的另一种泛化。Munarini图的主要优势之一在于，与之前提出的泛化不同，它们是雏菊立方体，正如斐波那契立方体和Pell图一样。在这篇第一篇文章中，我们研究了它们的一些基本性质，包括大小、递归结构、立方体多项式和最大立方体多项式。

## 引言

这项工作献给2024年逝去的Emanuele Munarini。Emanuele引入了Pell图[1]，并且是斐波那契立方体结构和枚举性质开创性论文的合著者[2]。因此，将这里引入的这些图的泛化以他的名字命名是很自然的。

斐波那契字符串是没有连续1的二进制字符串。维度为n的斐波那契立方体，记为Γn，是由长度为n的斐波那契字符串在超立方体Qn中所诱导的子图。

斐波那契立方体由W.-J. Hsu于1993年作为互连网络模型引入[3]。此后，它们被广泛应用于众多领域，并且也被证明具有独立组合学意义。2013年，Sandi Klav?ar撰写了一篇关于斐波那契立方体的综述文章[4]，最近一本关于它们的完整著作也已出版[5]。

对斐波那契立方体性质的研究吸引了许多研究者，并导致了各种有趣泛化和变体的发展，这些内容在[5]整章中都有涵盖。这些图族包括Lucas立方体、广义斐波那契立方体、Pell图、k-斐波那契立方体、Fibonacci p-立方体和Fibonacci-run图。

斐波那契立方体的结构与斐波那契数密切相关：F0=0, F1=1, Fn=Fn?1+Fn?2（n≥2）。它们的泛化之一是k-斐波那契序列，对于正整数k定义为Fn,k=kFn?1,k+Fn?2,k（n≥2），初始值为F0,k=0和F1,k=1。因此，1-斐波那契序列就是斐波那契序列。如果k=2，我们得到另一个著名序列，即Pell数Pn，其中P0=0, P1=1, Pn=2Pn?1+Pn?2（n≥2）。

受Pell序列启发，Emanuele Munarini [1]引入了定义在Pell字符串上的Pell图Πn，Pell字符串是字母表{0, 1, 2}上长度为n的字符串集合的子集。Πn的结构反映了递推关系Pn=2Pn?1+Pn?2。斐波那契立方体和Pell图[5, 定理9.68]属于雏菊立方体类[6]，这是超立方体的一类等距子图。

最近，受k≥2的k-斐波那契数启发，Vesna Ir?i?、Sandi Klav?ar和Elif Tan [7]提出了Pell图的泛化——广义Pell图Πn,k。我们将在后面的推论4.5中证明，对于k≥3和n≥2，Πn,k不是雏菊立方体。

同样受k-斐波那契数启发，Tomislav Do?li?和Luka Podrug [8]研究了第二个图族——金属立方体Πnk，它与Πn,k具有相同的阶数和大小。然而，它们并不构成Pell图的泛化，因为对于n≥3，Πn2与Pell图Πn不同构。此外，金属立方体也不总是雏菊立方体，通过直接检查[8]中的Π23和Π32（图1和图2）可以观察到这一点。

在本文中，我们引入了一个图族，我们称之为Munarini图Mn,k。这些图与广义Pell图具有相同的阶数和大小，但与它们不同，它们是雏菊立方体。Munarini图的归纳结构是对递推关系Fn,k=kFn?1,k+Fn?2,k的另一种解释。事实上，Mn,k是由Mn?2,k和k个Mn?1,k的副本沿着星形Sk?1连接而成的，而在Πn,k和Πnk中，维度为n?1的k个子图形成一条路径Pk（见图2）。此外，Munarini图同时推广了斐波那契立方体和Pell图，因为Mn,1?Γn?1且Mn,2?Πn。

我们将研究Munarini图的基本性质，并表明它们的若干枚举性质得出的公式与斐波那契立方体和Pell图的公式非常接近。

本文的组织如下。在下一节中，我们正式定义本文中使用的概念并固定一些符号。然后我们引入Munarini图Mn,k并确定它们的初始性质，如边的数量和递归结构。在第3节中，我们研究Mn,k作为超立方体和斐波那契立方体的子图。在第4节中，我们确定立方体多项式，并研究Mn,k中的超立方体和最大超立方体。

## 预备知识

我们现在介绍本文所需的Concept和符号。

在本文中，我们使用带点并符号A∪?B或??k≥0Ak来强调这些集合是不相交的。

设k≥1。长度为l(s)的(k+1)-元字符串s（简称字符串）是{0,1,…,k}中l(s)个字符的序列。设i∈{0,1,…,k}，则|s|i表示i在s中出现的次数。字母表是经典上称为字母的符号集合；在我们的上下文中，这些字母本身可能是(k+1)-元字符串。例如Σ={……}。

## Munarini图作为超立方体的子图

介绍以下二进制字符串集合是有益的。令A0=0k，对于i∈{1,…,k}，令Ai=0i?110k?i。

对于给定的k≥1，Munarini字符串是由集合{0k, 10k?1, 010k?2, …, 0k?210, 0k?110k}={A0, A1, …, Ak?1, AkA0}生成的二进制字符串。

注意这些字符串是长度为k的倍数的斐波那契字符串，对于n≥0，我们用Fn,k?表示长度为kn的Munarini字符串的集合。等价地，Munarini字符串是满足约束条件的幺半群（由A={A0, A1, …, Ak}生成）中的元素……

## 超立方体作为Munarini图的子图

由于Munarini图是雏菊立方体，一旦知道权重多项式，它们的立方体多项式和最大立方体多项式就可以轻易确定。这是本节的主要目的。

对于一个图G，设cp(G)（p≥0）表示G的同构于Qp的诱导子图的数量。G的立方体多项式CG(x)是对应的计数多项式，即CG(x)=∑p≥0cp(G)xp。

这个多项式在[17]中引入，并在[18]中确定了斐波那契立方体和Lucas立方体的情况，之后又确定了……

## 结论

在本文中，我们引入了Munarini图，它是斐波那契立方体和Pell图的泛化，并研究了它们的初始性质。这些结果表明Munarini图与斐波那契立方体和Pell图共享若干结构和枚举性质，进一步支持了它们作为雏菊立方体类中自然泛化的作用。

在后续论文中，我们将确定直径、半径，以及给定度数或偏心距的顶点数量，并以一些……作为结论。

Michel Mollard