TOPICS
Search

Distance Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The distance polynomial is the characteristic polynomial of the graph distance matrix.

The following table summarizes distance polynomials for some common classes of graphs.

graphdistance polynomial
barbell graph(1+x)^(2n-4)(n+2nx+x^2)[(2+x)^2-n(5+4x)]
book graph S_(n+1) square P_2x(x(4+x))^(n-1)(1+n+x)((-1+x)(4+x)-n(4+5x))
cocktail party graph K_(n×2)((x(2+x))^n(-2n+x))/x
complete graph K_n(-1-x)^(n-1)(-1+n-x)
complete bipartite graph K_(n,n)(2+x)^(2n-2)(2-3n+x)(2-n+x)
complete tripartite graph K_(n,n,n)(-1)^n(x-(4n-2))(x-(n-2))^2(2+x)^(3(n-1))
crown graph(-4+n-x)(3n-x)(x(4+x))^(n-1)
halved cube graph for n>2(x-2^(n-3)n)x^(2^(n-1)-n-1)(2^(n-3)+x)^n
hypercube graph Q_n(x-2^(n-1)n)x^(2^n-n-1)(2^(n-1)+x)^n
path graph 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 rook graph(-1)^n(x-2(n-1)n)x^((n-1)^2)(n+x)^(2(n-1))
star graph S_n(-2-x)^((-2+n))(1+x(4+x)-n(1+2x))

The following table summarizes the recurrence relations for distance polynomials for some simple classes of graphs.

graphorderrecurrence
barbell graph3p_n(x)=(x+1)^6p_(n-3)(x)-3(x+1)^4p_(n-2)(x)+3(x+1)^2p_(n-1)(x)
book graph 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)
cocktail party graph K_(n×2)2p_n(x)=2x(x+2)p_(n-1)(x)-x^2(x+2)^2p_(n-2)(x)
complete graph K_n2p_n(x)=(x+1)^2(-p_(n-2)(x))-2(x+1)p_(n-1)(x)
complete bipartite graph 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)
complete tripartite graph 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)
crown graph3p_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)
ladder graph 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)
path graph 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)
star graph S_n2p_n(x)=(x+2)^2(-p_(n-2)(x))-2(x+2)p_(n-1)(x)
wheel graph 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)

See also

Characteristic Polynomial, Graph Distance Matrix

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Distance Polynomial

Cite this as:

Weisstein, Eric W. "Distance Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DistancePolynomial.html

Subject classifications