Inverting non-invertible trees

MaRDI QIDQ6295866zbMATH OpenFDO

Authors S. Pavlíková, Jozef Širáň

Publication date 30 December 2017

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Theory of matrix inversion and generalized inverses (15A09) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: If a graph has a non-singular adjacency matrix, then one may use the inverse matrix to define a (labeled) graph that may be considered to be the inverse graph to the original one. It has been known that an adjacency matrix of a tree is non-singular if and only if the tree has a unique perfect matching; in this case the determinant of the matrix turns out to be $pm1$ and the inverse of the tree was shown to be `switching-equivalent' to a simple graph [C. Godsil, Inverses of Trees, Combinatorica 5 (1985), 33--39]. Using generalized inverses of symmetric matrices (that coincide with Moore-Penrose, Drazin, and group inverses in the symmetric case) we prove a formula for determining a `generalized inverse' of a tree.

This page was built for publication: Inverting non-invertible trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6295866)