主題
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-三格骨牌圖

另請參閱

斐波那契數, 超立方體圖, 盧卡斯立方體圖, 佩爾圖, 策肯多夫表示

使用 探索

參考文獻

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. "斐波那契立方體圖。" 來自 Web 資源。 https://mathworld.tw/FibonacciCubeGraph.html

主題分類