主题
Search

斐波那契立方体图

FibonacciCubeGraph

阶为 n 的斐波那契立方体图 F_n 是一个具有 F_(n+2) 个顶点的图，其中 F_n 是一个 斐波那契数，由数字 0 到 F_(n+2)-1 的 策肯多夫表示 标记，并且当且仅当 (iff) 它们的标签相差一位时（即，如果它们之间的 汉明距离 正好为 1）两个顶点通过边连接。阶为 n 的斐波那契立方体可以表示为 Gamma_n (Munarini et al. 2001, Munarini 2019)。F_n 也是 路径补图 P^__n 的 单纯形图 (Alikhani and Ghanbari 2024)。

阶为 n 的斐波那契立方体图具有边数

m(F_n)=2(n+1)F_n+nF_(n+1)
(1)
=1/(10)[(5n+4)F_n+nL_n,
(2)

其中 F_n 是一个 斐波那契数，而 L_n 是一个 卢卡斯数。

斐波那契立方体图是可追溯的和二分的。n-斐波那契立方体图对于 n=4, 7, 10, .... 是哈密顿图。斐波那契立方体图也是中值图 (Klavžar 2005, Došlić and Podrug 2023)。

斐波那契立方体已被推广到顶点计数由各种高阶斐波那契数计数的图 (Hsu and Chung 1993, Došlić and Podrug 2023)。

特殊情况总结在下表中。

n图
1路径图 P_2
2路径图 P_3
3横幅图
4L-三格骨牌图

另请参阅

斐波那契数, 超立方体图, 卢卡斯立方体图, 佩尔图, 策肯多夫表示

使用 Wolfram|Alpha 探索

参考文献

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Castro, A.; Klavžar, S.; Mollard, M.; and Rho, T. "On the Domination Number and the 2-Packing Number of Fibonacci Cubes and Lucas Cubes." Comput. Math. Appl. 61, 2655-2660, 2011.Castro, A. and Mollard, M. "The Eccentricity Sequences of Fibonacci and Lucas Cubes." Disc. Math. 312, 1025-1037, 2012.Dedò, E.; Torri, D.; and Salvi, N. Z. "The Observability of the Fibonacci and the Lucas Cubes." Disc. Math. 255, 55-63, 2002.Došlić, T. and Podrug, L. "Metallic Cubes." 26 Jul 2023. https://arxiv.org/abs/2307.14054.Hsu, W. J. "Fibonacci Cubes: A New Class of Interconnection Topologies for Parallel Processing." IEEE Trans. Parallel and Distributed Systems 4, 3-12, 1993.Hsu, W. J. and Chung, M. J. "Generalized Fibonacci Cubes." Proc. Internat. Conf. Parallel Processing (1993), 299-303, 1993.Hsu, W.-J.; Page, C. V.; and Liu, J.-S. "Fibonacci Cubes: A Class of Self-Similar Graphs." Fib. Quart. 31, 65-72, 1993.Ilić, A. and Milošević, M. "The Parameters of Fibonacci and Lucas Cubes." Ars Math. Contemp. 12, 25-29, 2017.Klavžar, S. "On Median Nature and Enumerative Properties of Fibonacci-Like Cubes." Disc. Math. 299, 145-153, 2005.Klavžar, S. and Mollard, M. "Wiener Index and Hosoya Polynomial of Fibonacci and Lucas Cubes." MATCH Commun. Math. Comput. Chem. 68, 311-324, 2012.Klavžar, S. and Mollard, M. "Asymptotic Properties of Fibonacci Cubes and Lucas Cubes." Ann. Combin. 18, 447-457, 2014.Klavžar, S.; Mollard, M.; and Petkovšek, M. "The Degree Sequence of Fibonacci and Lucas Cubes." Disc. Math. 311, 1310-1322, 2001.Munarini, E. "Pell Graphs." Disc. Math. 342, 2415-2428, 2019.Munarini, E. and Salvi, N. Z. "Structural and Enumerative Properties of the Fibonacci Cubes." Disc. Math. 255, 317-324, 2022.Munarini, E.; Cippo, C. P.; and Salvi, N. Z. "On the Lucas Cubes." Fibonacci Quart. 39, 12-21, 2001.Taranenko, A. and Vesel, A. "Fast Recognition of Fibonacci Cubes." Algorithmica 49, 81-93, 2007.

引用为

Weisstein, Eric W. "斐波那契立方体图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/FibonacciCubeGraph.html

主题分类