主题
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.net.cn/DistancePolynomial.html

主题分类