主題
Search

距離多項式

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

距離多項式是 特徵多項式 的 圖距離矩陣。

下表總結了一些常見圖類的距離多項式。

圖距離多項式
啞鈴圖(1+x)^(2n-4)(n+2nx+x^2)[(2+x)^2-n(5+4x)]
書圖 S_(n+1) square P_2x(x(4+x))^(n-1)(1+n+x)((-1+x)(4+x)-n(4+5x))
雞尾酒會圖 K_(n×2)((x(2+x))^n(-2n+x))/x
完全圖 K_n(-1-x)^(n-1)(-1+n-x)
完全二部圖 K_(n,n)(2+x)^(2n-2)(2-3n+x)(2-n+x)
完全三部圖 K_(n,n,n)(-1)^n(x-(4n-2))(x-(n-2))^2(2+x)^(3(n-1))
冠圖(-4+n-x)(3n-x)(x(4+x))^(n-1)
半立方體圖 for n>2(x-2^(n-3)n)x^(2^(n-1)-n-1)(2^(n-3)+x)^n
超立方體圖 Q_n(x-2^(n-1)n)x^(2^n-n-1)(2^(n-1)+x)^n
路徑圖 P_n1/4[2(-x)^n+(-1-x-sqrt(1+2x))^n+(-1+x+sqrt(1+2x))^n+(n[(-1-x+sqrt(2x))^n-(-1-x-sqrt(1+2x))^n])/(sqrt(1+2x))]
n×n 車圖(-1)^n(x-2(n-1)n)x^((n-1)^2)(n+x)^(2(n-1))
星圖 S_n(-2-x)^((-2+n))(1+x(4+x)-n(1+2x))

下表總結了一些簡單圖類的距離多項式遞推關係。

圖階數遞推關係
啞鈴圖3p_n(x)=(x+1)^6p_(n-3)(x)-3(x+1)^4p_(n-2)(x)+3(x+1)^2p_(n-1)(x)
書圖 S_(n+1) square P_23p_n(x)=x^3(x+4)^3p_(n-3)(x)-3x^2(x+4)^2p_(n-2)(x)+3x(x+4)p_(n-1)(x)
雞尾酒會圖 K_(n×2)2p_n(x)=2x(x+2)p_(n-1)(x)-x^2(x+2)^2p_(n-2)(x)
完全圖 K_n2p_n(x)=(x+1)^2(-p_(n-2)(x))-2(x+1)p_(n-1)(x)
完全二部圖 K_(n,n)3p_n(x)=(x+2)^6p_(n-3)(x)-3(x+2)^4p_(n-2)(x)+3(x+2)^2p_(n-1)(x)
完全三部圖 K_(n,n,n)4p_n(x)=(x+2)^(12)(-p_(n-4)(x))-4(x+2)^9p_(n-3)(x)-6(x+2)^6p_(n-2)(x)-4(x+2)^3p_(n-1)(x)
冠圖3p_n(x)=x^3(x+4)^3p_(n-3)(x)-3x^2(x+4)^2p_(n-2)(x)+3x(x+4)p_(n-1)(x)
梯子圖 P_2 square P_n8p_n(x)=x^(16)(-p_(n-8)(x))+4(2x+3)x^(13)p_(n-7)(x)-4(7x^2+18x+12)x^2p_(n-2)(x)-4(7x^2+18x+12)x^(10)p_(n-6)(x)+4(14x^3+45x^2+48x+16)x^3p_(n-3)(x)+4(14x^3+45x^2+48x+16)x^7p_(n-5)(x)-2(35x^3+120x^2+144x+64)x^5p_(n-4)(x)+4(2x+3)xp_(n-1)(x)
路徑圖 P_n5p_n(x)=x^5(-p_(n-5)(x))-(5x+4)x^3p_(n-4)(x)-2(5x^2+6x+2)xp_(n-3)(x)-2(5x^2+6x+2)p_(n-2)(x)-(5x+4)p_(n-1)(x)
星圖 S_n2p_n(x)=(x+2)^2(-p_(n-2)(x))-2(x+2)p_(n-1)(x)
輪圖 W_n6p_n(x)=2(x^2+2x+2)p_(n-3)(x)-p_(n-6)(x)-2(x+1)p_(n-5)(x)-(x-1)(x+1)p_(n-4)(x)-(x-1)(x+1)p_(n-2)(x)-2(x+1)p_(n-1)(x)

另請參閱

特徵多項式, 圖距離矩陣

使用 探索

參考文獻

Aouchiche, M. and Hansen, P. "Distance Spectra of Graphs: A Survey." Linear Algebra Appl. 458, 301-386, 2014.Balaji, R. and Bapat, R. B. "On Euclidean Distance Matrices." Linear Algebra Appl. 424< 108-117, 2007.Bapat, R. B. Ch. 3 in Graphs and Matrices. New Delhi, India: Springer, 2010.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 96-97, 2000.Ruzieh, S. and Powers, D. L. "The Distance Spectrum of the Path P_n and the First Distance Eigenvector of Connected Graphs." Linear Multilinear Algebra 28, 75-81, 1990.Steinerberger, S. "The First Eigenvector of a Distance Matrix Is Nearly Constant." Disc. Math. 346, 113291, 2023.

在 中被引用

距離多項式

引用為

韋斯坦, 埃裡克 W. "距離多項式." 來自 --一個 Wolfram 網路資源。 https://mathworld.tw/DistancePolynomial.html

主題分類