NumberDB$^\beta$ Advanced search Tags Tables Help Login
Distance characteristic polynomials of connected graphs
edit · history · discussion · files · long url · combinatorics eigenvalue polynomial
Polynomials
$G$ 
$p_{\mathcal D}(G,x)$
A_:
x^2 - 1
comment: This is the complete graph $K_2$.
BW:
x^3 - 6*x - 4
comment: This is the path $P_3$.
Bw:
x^3 - 3*x - 2
comment: This is the complete graph $K_3$.
CF:
x^4 - 15*x^2 - 28*x - 12
comment: This is the star $K_{1,3}$.
CL:
x^4 - 20*x^2 - 32*x - 12
comment: This is the path $P_4$.
CN:
x^4 - 12*x^2 - 18*x - 7
C]:
x^4 - 12*x^2 - 16*x
comment: This is the cycle $C_4$.
C^:
x^4 - 9*x^2 - 12*x - 4
comment: This is the diamond graph.
C~:
x^4 - 6*x^2 - 8*x - 3
comment: This is the complete graph $K_4$.
D?{:
x^5 - 28*x^3 - 88*x^2 - 96*x - 32
comment: This is the star $K_{1,4}$.
D@s:
x^5 - 38*x^3 - 116*x^2 - 112*x - 32
D@{:
x^5 - 25*x^3 - 70*x^2 - 66*x - 20
DBg:
x^5 - 50*x^3 - 140*x^2 - 120*x - 32
comment: This is the path $P_5$.
DBk:
x^5 - 30*x^3 - 82*x^2 - 72*x - 20
comment: This is the bull graph.
DB{:
x^5 - 22*x^3 - 56*x^2 - 46*x - 12
comment: This is the dart graph.
DFw:
x^5 - 22*x^3 - 52*x^2 - 24*x + 16
comment: This is the complete bipartite graph $K_{2,3}$.
DF{:
x^5 - 19*x^3 - 46*x^2 - 36*x - 8
DIk:
x^5 - 30*x^3 - 76*x^2 - 48*x
DJk:
x^5 - 27*x^3 - 64*x^2 - 50*x - 12
DJ{:
x^5 - 19*x^3 - 44*x^2 - 36*x - 10
DK[:
x^5 - 35*x^3 - 88*x^2 - 74*x - 20
DK{:
x^5 - 22*x^3 - 52*x^2 - 43*x - 12
comment: This is the butterfly graph.
DLo:
x^5 - 25*x^3 - 60*x^2 - 35*x - 6
comment: This is the cycle $C_5$.
DL{:
x^5 - 19*x^3 - 42*x^2 - 29*x - 6
DNw:
x^5 - 19*x^3 - 40*x^2 - 18*x + 4
DN{:
x^5 - 16*x^3 - 34*x^2 - 25*x - 6
comment: This is the house X graph.
D]{:
x^5 - 16*x^3 - 32*x^2 - 16*x
comment: This is the wheel $W_5$.
D^{:
x^5 - 13*x^3 - 26*x^2 - 18*x - 4
Dbk:
x^5 - 22*x^3 - 50*x^2 - 28*x
comment: This is the house graph.
D~{:
x^5 - 10*x^3 - 20*x^2 - 15*x - 4
comment: This is the complete graph $K_5$.
E?Bw:
x^6 - 45*x^4 - 200*x^3 - 360*x^2 - 288*x - 80
comment: This is the star $K_{1,5}$.
E?Fg:
x^6 - 60*x^4 - 272*x^3 - 468*x^2 - 336*x - 80
E?Fw:
x^6 - 42*x^4 - 174*x^3 - 285*x^2 - 204*x - 52
E?NG:
x^6 - 65*x^4 - 296*x^3 - 504*x^2 - 352*x - 80
E?NW:
x^6 - 52*x^4 - 218*x^3 - 345*x^2 - 228*x - 52
E?Nw:
x^6 - 39*x^4 - 152*x^3 - 228*x^2 - 144*x - 32
E?]o:
x^6 - 64*x^4 - 248*x^3 - 320*x^2 - 128*x
E?]w:
x^6 - 44*x^4 - 172*x^3 - 252*x^2 - 152*x - 32
E?^o:
x^6 - 44*x^4 - 160*x^3 - 180*x^2 - 16*x + 48
E?^w:
x^6 - 36*x^4 - 134*x^3 - 189*x^2 - 108*x - 20
E?~o:
x^6 - 36*x^4 - 128*x^3 - 144*x^2 + 64
comment: This is the complete bipartite graph $K_{2,4}$.
E?~w:
x^6 - 33*x^4 - 120*x^3 - 168*x^2 - 96*x - 16
E@FG:
x^6 - 84*x^4 - 368*x^3 - 580*x^2 - 368*x - 80
E@JW:
x^6 - 52*x^4 - 208*x^3 - 288*x^2 - 128*x
E@NW:
x^6 - 49*x^4 - 188*x^3 - 268*x^2 - 160*x - 32
E@Nw:
x^6 - 36*x^4 - 132*x^3 - 189*x^2 - 120*x - 28
E@QW:
x^6 - 77*x^4 - 356*x^3 - 572*x^2 - 368*x - 80
E@Rw:
x^6 - 39*x^4 - 148*x^3 - 217*x^2 - 140*x - 33
E@UW:
x^6 - 57*x^4 - 248*x^3 - 384*x^2 - 240*x - 52
E@Vw:
x^6 - 36*x^4 - 130*x^3 - 174*x^2 - 94*x - 17
E@YO:
x^6 - 105*x^4 - 448*x^3 - 648*x^2 - 384*x - 80
comment: This is the path $P_6$.
E@YW:
x^6 - 57*x^4 - 232*x^3 - 304*x^2 - 128*x
E@]o:
x^6 - 61*x^4 - 228*x^3 - 304*x^2 - 168*x - 32
E@]w:
x^6 - 41*x^4 - 152*x^3 - 212*x^2 - 128*x - 28
E@^W:
x^6 - 41*x^4 - 146*x^3 - 188*x^2 - 98*x - 17
E@^o:
x^6 - 41*x^4 - 140*x^3 - 152*x^2 - 40*x + 12
E@^w:
x^6 - 33*x^4 - 114*x^3 - 149*x^2 - 84*x - 17
E@`w:
x^6 - 57*x^4 - 236*x^3 - 360*x^2 - 232*x - 52
E@ow:
x^6 - 62*x^4 - 250*x^3 - 373*x^2 - 236*x - 52
E@vw:
x^6 - 33*x^4 - 112*x^3 - 138*x^2 - 64*x - 8
E@~o:
x^6 - 33*x^4 - 108*x^3 - 108*x^2 + 32
E@~w:
x^6 - 30*x^4 - 100*x^3 - 127*x^2 - 68*x - 12
EAMw:
x^6 - 49*x^4 - 192*x^3 - 273*x^2 - 160*x - 32
EA]o:
x^6 - 49*x^4 - 176*x^3 - 209*x^2 - 80*x
EBYW:
x^6 - 49*x^4 - 184*x^3 - 216*x^2 - 32*x + 48
EBYw:
x^6 - 41*x^4 - 144*x^3 - 165*x^2 - 44*x + 12
EBZw:
x^6 - 33*x^4 - 112*x^3 - 132*x^2 - 48*x
EB]w:
x^6 - 38*x^4 - 130*x^3 - 166*x^2 - 90*x - 17
EB^w:
x^6 - 30*x^4 - 98*x^3 - 121*x^2 - 64*x - 12
EBhw:
x^6 - 46*x^4 - 160*x^3 - 199*x^2 - 100*x - 17
EBjW:
x^6 - 36*x^4 - 120*x^3 - 133*x^2 - 48*x
EBjw:
x^6 - 33*x^4 - 108*x^3 - 127*x^2 - 60*x - 9
EBnW:
x^6 - 33*x^4 - 108*x^3 - 123*x^2 - 54*x - 8
EBn_:
x^6 - 36*x^4 - 118*x^3 - 114*x^2 - 10*x + 7
EBnw:
x^6 - 30*x^4 - 96*x^3 - 112*x^2 - 54*x - 9
EB~o:
x^6 - 30*x^4 - 92*x^3 - 84*x^2 + 16
EB~w:
x^6 - 27*x^4 - 84*x^3 - 98*x^2 - 48*x - 8
ECXw:
x^6 - 54*x^4 - 204*x^3 - 280*x^2 - 160*x - 32
EC\w:
x^6 - 46*x^4 - 170*x^3 - 229*x^2 - 124*x - 20
EENg:
x^6 - 36*x^4 - 122*x^3 - 129*x^2 - 12*x + 28
EFz_:
x^6 - 33*x^4 - 104*x^3 - 72*x^2 + 96*x + 112
comment: This is the complete bipartite graph $K_{3,3}$.
EFzw:
x^6 - 27*x^4 - 80*x^3 - 72*x^2 + 16
EF~w:
x^6 - 24*x^4 - 72*x^3 - 81*x^2 - 36*x - 4
EGNW:
x^6 - 44*x^4 - 162*x^3 - 201*x^2 - 80*x
EGcw:
x^6 - 69*x^4 - 280*x^3 - 405*x^2 - 244*x - 52
EGdo:
x^6 - 81*x^4 - 308*x^3 - 424*x^2 - 248*x - 52
EGdw:
x^6 - 49*x^4 - 182*x^3 - 253*x^2 - 152*x - 33
EHQW:
x^6 - 52*x^4 - 198*x^3 - 250*x^2 - 114*x - 17
EHUW:
x^6 - 49*x^4 - 180*x^3 - 220*x^2 - 80*x
EHuw:
x^6 - 33*x^4 - 106*x^3 - 108*x^2 - 22*x + 7
EI]w:
x^6 - 38*x^4 - 124*x^3 - 136*x^2 - 48*x
EI_w:
x^6 - 69*x^4 - 268*x^3 - 340*x^2 - 128*x
EIe_:
x^6 - 57*x^4 - 200*x^3 - 144*x^2
comment: This is the cycle $C_6$.
EImo:
x^6 - 41*x^4 - 136*x^3 - 120*x^2 + 32*x + 48
EImw:
x^6 - 38*x^4 - 122*x^3 - 125*x^2 - 28*x + 12
EIno:
x^6 - 33*x^4 - 104*x^3 - 93*x^2 + 12*x + 28
EInw:
x^6 - 30*x^4 - 94*x^3 - 99*x^2 - 28*x + 4
EJYW:
x^6 - 46*x^4 - 154*x^3 - 165*x^2 - 44*x + 12
EJ]w:
x^6 - 35*x^4 - 110*x^3 - 132*x^2 - 68*x - 12
EJ^w:
x^6 - 27*x^4 - 84*x^3 - 105*x^2 - 60*x - 13
EJeg:
x^6 - 41*x^4 - 132*x^3 - 140*x^2 - 48*x
EJmw:
x^6 - 35*x^4 - 108*x^3 - 125*x^2 - 60*x - 9
EJnW:
x^6 - 30*x^4 - 90*x^3 - 88*x^2 - 24*x
EJnw:
x^6 - 27*x^4 - 80*x^3 - 87*x^2 - 38*x - 5
EJqw:
x^6 - 33*x^4 - 102*x^3 - 101*x^2 - 24*x + 7
EJ~o:
x^6 - 27*x^4 - 78*x^3 - 72*x^2 - 12*x + 8
EJ~w:
x^6 - 24*x^4 - 70*x^3 - 81*x^2 - 42*x - 8
EKNG:
x^6 - 49*x^4 - 168*x^3 - 144*x^2
EK\w:
x^6 - 43*x^4 - 140*x^3 - 173*x^2 - 92*x - 17
EK]w:
x^6 - 38*x^4 - 120*x^3 - 135*x^2 - 60*x - 9
EK^w:
x^6 - 30*x^4 - 92*x^3 - 105*x^2 - 50*x - 8
EK`w:
x^6 - 49*x^4 - 172*x^3 - 204*x^2 - 80*x
EK~o:
x^6 - 30*x^4 - 88*x^3 - 79*x^2 - 8*x + 12
EK~w:
x^6 - 27*x^4 - 80*x^3 - 93*x^2 - 48*x - 9
ELpw:
x^6 - 33*x^4 - 102*x^3 - 97*x^2 - 24*x
ELrw:
x^6 - 30*x^4 - 90*x^3 - 90*x^2 - 36*x - 5
comment: This is the wheel $W_6$.
ELv_:
x^6 - 33*x^4 - 100*x^3 - 84*x^2
EL~o:
x^6 - 27*x^4 - 76*x^3 - 63*x^2 - 4*x + 4
EL~w:
x^6 - 24*x^4 - 68*x^3 - 72*x^2 - 32*x - 5
ENzw:
x^6 - 24*x^4 - 66*x^3 - 59*x^2 - 12*x + 4
EN~w:
x^6 - 21*x^4 - 58*x^3 - 63*x^2 - 30*x - 5
EPTW:
x^6 - 66*x^4 - 238*x^3 - 309*x^2 - 168*x - 32
ER^W:
x^6 - 30*x^4 - 90*x^3 - 86*x^2 - 18*x + 7
E]~o:
x^6 - 24*x^4 - 64*x^3 - 48*x^2
E]~w:
x^6 - 21*x^4 - 56*x^3 - 52*x^2 - 16*x
E^~w:
x^6 - 18*x^4 - 48*x^3 - 51*x^2 - 24*x - 4
E_Nw:
x^6 - 36*x^4 - 126*x^3 - 167*x^2 - 96*x - 20
E_]o:
x^6 - 39*x^4 - 136*x^3 - 147*x^2 - 28*x + 4
E_]w:
x^6 - 36*x^4 - 124*x^3 - 144*x^2 - 48*x
E`Lw:
x^6 - 51*x^4 - 174*x^3 - 228*x^2 - 132*x - 28
E`NG:
x^6 - 59*x^4 - 204*x^3 - 269*x^2 - 156*x - 33
E`NW:
x^6 - 46*x^4 - 152*x^3 - 191*x^2 - 104*x - 20
E`Nw:
x^6 - 33*x^4 - 106*x^3 - 135*x^2 - 78*x - 17
E`]o:
x^6 - 36*x^4 - 116*x^3 - 120*x^2 - 44*x - 5
E`]w:
x^6 - 33*x^4 - 104*x^3 - 112*x^2 - 40*x
EaMw:
x^6 - 41*x^4 - 136*x^3 - 145*x^2 - 48*x
Ebnw:
x^6 - 27*x^4 - 78*x^3 - 76*x^2 - 24*x
Ejmw:
x^6 - 27*x^4 - 76*x^3 - 61*x^2 + 4*x + 15
Ek]w:
x^6 - 30*x^4 - 88*x^3 - 75*x^2 - 4*x + 7
EoLW:
x^6 - 44*x^4 - 150*x^3 - 162*x^2 - 66*x - 9
Es\w:
x^6 - 30*x^4 - 90*x^3 - 69*x^2 + 36*x + 44
E~~w:
x^6 - 15*x^4 - 40*x^3 - 45*x^2 - 24*x - 5
comment: This is the complete graph $K_6$.
Definition
The distance characteristic polynomial $p_{\mathcal D}(G,x)$ of a finite, simple, undirected, connected, unweighted graph $G$ is $\det(xI_n-\mathcal D(G))$, where $n=|V(G)|$ and $\mathcal D(G)_{uv}=d_G(u,v)$ is the number of edges in a shortest path, with $d_G(u,u)=0$ [1].
Parameters
$G$
—   graph (a connected simple graph on at least two vertices, identified by its graph6 string after Sage canonical_label(algorithm='sage'))
Formulas
(1)
For a graph on $n\geq2$ vertices, $[x^{n-1}]p_{\mathcal D}(G,x)=0$ and $[x^{n-2}]p_{\mathcal D}(G,x)=-\sum_{\{u,v\}\subseteq V(G)}d_G(u,v)^2$. The sum is over unordered pairs of distinct vertices.
(2)
For the complete graph $K_n$, $p_{\mathcal D}(K_n,x)=(x-n+1)(x+1)^{n-1}$ [1].
(3)
For the complete bipartite graph $K_{a,b}$ with $a,b\geq1$, $p_{\mathcal D}(K_{a,b},x)=(x+2)^{a+b-2}\bigl((x-2a+2)(x-2b+2)-ab\bigr)$. Vectors constant on each part give the quotient matrix $\begin{pmatrix}2(a-1)&b\\a&2(b-1)\end{pmatrix}$; vectors summing to zero within a part have eigenvalue $-2$.
(4)
For every tree $T$ on $n\geq2$ vertices, $p_{\mathcal D}(T,0)=-(n-1)2^{n-2}$, by the Graham-Pollak distance determinant formula [1].
(5)
For the path $P_n$, ordering vertices along the path gives $\mathcal D(P_n)_{ij}=|i-j|$. Thus $p_{\mathcal D}(P_n,x)$ equals the Fiedler characteristic polynomial in the classical test matrices.
Comments
(6)
Graphs are identified by their graph6 strings [2] after G.canonical_label(algorithm='sage'). Recover a graph with Graph(key, format='graph6'); use a raw string literal for a key containing a backslash. The identities agree with the adjacency characteristic polynomials and the Laplacian polynomials. Entries are ordered by vertex count and then by graph6 string.
(7)
The convention is monic. The historical convention $\det(\mathcal D(G)-xI_n)$ is $(-1)^n p_{\mathcal D}(G,x)$ [1]. The one-vertex graph has polynomial $x$.
(8)
The roots are the real eigenvalues of $\mathcal D(G)$, counted with algebraic multiplicity. The largest root is the distance spectral radius.
(9)
The selection is the complete connected-graph census on two through six vertices [3]. Common graph names annotate 26 entries. For a wheel $W_n$, $n$ includes the hub.
Programs
(P1)
Sage
import numberdb.sage
from sage.graphs.graph import Graph
from sage.rings.integer_ring import ZZ

G = Graph('CL', format='graph6')  # the path P4
G.distance_matrix().change_ring(ZZ).charpoly('x')
# Stable graph identity:
G.canonical_label(algorithm='sage').graph6_string()
References
[1]
Leslie Hogben and Carolyn Reinhart, Spectra of variants of distance matrices of graphs and digraphs: a survey (2021), Sections 1, 2.2 and 5. (arXiv)
Links
Similar tables
Distance spectral radii of connected graphs —   stores the largest roots of these distance characteristic polynomials for the same graph identities
Characteristic polynomials of connected graphs —   uses adjacency matrices for the same graph identities
Laplacian polynomials of connected graphs —   uses combinatorial Laplacians for the same graph identities
Characteristic polynomials of the classical test matrices —   its Fiedler matrices are the distance matrices of paths
Data properties
Entries are of type: integral polynomial
How well the digits are known: exact
Table is complete: no (it holds all 142 connected simple graphs on two through six vertices, with counts 1, 2, 6, 21 and 112 by order. This complete small-order reference census covers trees, cyclic graphs, bipartite and non-bipartite graphs, and regular and irregular distance patterns for identifying shortest-path spectral calculations. Six vertices is a practical, noncanonical boundary; seven would add 853 graphs, mostly extending the census)
How they were obtained:

The generator computes each shortest-path distance matrix over $\mathbb{Z}$ and its monic characteristic polynomial in $\mathbb{Z}[x]$. Every coefficient is exact. The longest written polynomial has 46 characters.

more

The independent checker decodes graph6 directly, computes distances by Floyd-Warshall, and expands the determinant over permutations. After exact $K_2$ and $P_3$ controls, it agrees with all 142 polynomials. The coefficient identities and the reality of every root hold on all entries. The tree determinant identity agrees on all 13 trees; the complete-graph and complete-bipartite formulas agree on all 5 and 9 applicable graphs. All 5 paths agree with stored Fiedler polynomials. The largest roots lie in the written intervals of all 142 stored distance spectral radii, including exact equality for integer radii. The adjacency-spectrum relation for regular graphs of diameter at most two agrees on all 10 applicable graphs.

The canonical graph identities agree with the corresponding adjacency and Laplacian table keys and McKay's connected graph catalogues. The attached argument-selection.md explains the family and practical finite extent; checks.py and numerical-evidence.json retain the computations and measurements.



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.