Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Graph invariant — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · graph
  2. 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.

    part 2 · graph
  3. 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.

    part 3 · graph
  4. 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.

    part 4 · graph

All series