Graph elimination — where it appears
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Eliminating a vertex is a graph operation
Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Graph laplacianBackward errorCombinatorial preconditioningCospectral graphsDeterminantExact ground truthFillFloating pointGraph invariantInteger overflowMatrix tree theoremMinimum degree