论文标题
斐波那契运行图I：基本属性
Fibonacci-run graphs I: basic properties
论文作者
论文摘要
在互连网络的经典模型中，有超管和斐波那契立方体。斐波那契立方体是通过将设置的顶点限制为那些不包含连续1S的二进制字符串获得的超图的子图，该二进制字符串由fibonacci数字计算。另一组由斐波那契数计数的二进制字符串是对运行长度有限制的二进制字符串。由于顶点定义了斐波那契运行的图，因此在后一个字符串上的高立方体的诱导子图。它们具有与斐波那契多维数据集相同数量的顶点，但边缘更少和连接性能不同。 我们获得了斐波那契运行图的特性，包括边缘数量，基本递归的类似物，顶点的平均程度，hamiltonicity，特殊程度序列以及它们所包含的超管的数量。对斐波那契运行图的度序列的详细研究本身很有趣，并且在同伴论文中得到了报道。
Among the classical models for interconnection networks are hypercubes and Fibonacci cubes. Fibonacci cubes are induced subgraphs of hypercubes obtained by restricting the vertex set to those binary strings which do not contain consecutive 1s, counted by Fibonacci numbers. Another set of binary strings which are counted by Fibonacci numbers are those with a restriction on the runlengths. Induced subgraphs of the hypercube on the latter strings as vertices define Fibonacci-run graphs. They have the same number of vertices as Fibonacci cubes, but fewer edges and different connectivity properties. We obtain properties of Fibonacci-run graphs including the number of edges, the analogue of the fundamental recursion, the average degree of a vertex, Hamiltonicity, special degree sequences, and the number of hypercubes they contain. A detailed study of the degree sequences of Fibonacci-run graphs is interesting in its own right and is reported in a companion paper.
