Concept

Cospectral graphs — where it appears

Two non-isomorphic graphs with the same spectrum. The smallest Laplacian-cospectral pair has six vertices, so every method reading only eigenvalues answers a question about an equivalence class rather than about the graph it was handed.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as graph invariant — the same set of essays touches all of them, so they are one junction rather than several.

A count that comes out of a determinant

The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.

graph · graph elimination

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

graph · graph invariant

Named alongside it

The objects these essays reach for when they reach for this one.

Exact ground truth Graph invariant Graph laplacian Spanning tree Backward error Bipartite Characteristic polynomial Determinant Floating point Graph elimination Integer overflow Matrix tree theorem

All concepts