Numerical Linear Algebra
where the algebra stops being the arithmetic
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 5 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.

57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out

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 a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite

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 separated by the groupboth groups cyclic: cannot bethe same non-cyclic group6 vertices, 2 pairs117 vertices, 65 pairs3023128 vertices, 1022 pairs435361226a cyclic group is fixed by its order, and the order is the tree countthe group heard less than half the time

A finer invariant that hears less

The Laplacian spectrum fixes a graph's number of spanning trees and not the group those trees form, so the Smith normal form of the grounded Laplacian is a strictly finer integer invariant — and on the six-vertex pair the spectrum cannot separate, it does: ℤ₁₂ against ℤ₂ ⊕ ℤ₆. Over all 1,022 Laplacian-cospectral pairs of connected graphs on eight vertices it separates 435. The adjacency polynomial, a second spectrum rather than a finer one, separates all of them.

graph · Graph invariant top bar: same Laplacian spectrum · bottom bar: same adjacency spectrum0%25%50%75%100%share of cospectral pairs the invariant separatesLaplacian spectrum0%100%adjacency spectrum100%0%signless Laplacian spectrum89%100%spanning-tree count0%98%critical group43%98%degree sequence35%83%triangle count34%0%red: Laplacian-cospectral pairs · blue: adjacency-cospectraleach spectrum hears the other's pairs

Each spectrum hears the other's pairs

Pairs of graphs with the same Laplacian spectrum share a spanning-tree count, so the critical group could only tell them apart by how that count factors — and did on two pairs in five. Turn the census round, to the 733 pairs of eight-vertex graphs with the same adjacency spectrum, and the tree count is free to differ. It does on 717 of them, by a median of six per cent. The critical group separates exactly those 717 and not one more: on all sixteen pairs whose counts agree, including a non-cyclic one, the two graphs have the same group. And the Laplacian spectrum separates all 733, as the adjacency spectrum separated every Laplacian pair.

graph · Graph invariant the critical group, alonequartic pairs separated181of quartic pairs587cubic pairs separated014 vertices, degree 30 of 216 vertices, degree 30 of 2218 vertices, degree 30 of 5020 vertices, degree 30 of 4412 vertices, degree 436 of 12614 vertices, degree 497 of 30016 vertices, degree 448 of 161both groups cyclicseparated by the groupnot separatedbars: distinct pairs, split three waysthree in ten quartic, no cubic

The group hears a switch only at two

On a regular graph the Laplacian is the degree times the identity less the adjacency matrix, so the two spectra are one piece of information and the tree count comes with them; between cospectral regular graphs the critical group is the only exact invariant left. Made by Godsil–McKay switching on four vertices, 705 distinct cospectral pairs of 3- and 4-regular graphs on 12 to 20 vertices give its answer. It separates 181 of 587 quartic pairs and none of 118 cubic ones. And on every one of the 705 the two groups agree everywhere except at the prime two: a switch is a conjugation by a matrix of halves, the group can see it only through its 2-part, and a group whose tree count has fewer than three factors of two cannot see it at all.

graph · Graph invariant

Named alongside it

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

Graph invariantGraph laplacianSpanning-treeExact ground truthMatrix tree theoremCharacteristic polynomialInvariant factorsSmith normal formBackward errorBipartiteDeterminantExact arithmetic

All concepts