Geodesic
Reducing the adjacency matrix of a tree
The electronic journal of linear algebra, Tome 1 (1996), pp. 34-43.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Let T be a tree, A its adjacency matrix, and ff a scalar. We describe a linear-time algorithm for reducing the matrix ffI n + A. Applications include computing the rank of A, finding a maximum matching in T , computing the rank and determinant of the associated neighborhood matrix, and computing the characteristic polynomial of A.
Classification : 05C05, 15A15, 15A18, 68R10
Keywords: tree, graph, adjacency matrix, determinant, rank, eigenvalue $AMS(MOS)$ subject 
@article{ELA_1996__1__a3,
     author = {Fricke, Gerd H. and Hedetniemi, Stephen T. and Jacobs, David P. and Trevisan, Vilmar},
     title = {Reducing the adjacency matrix of a tree},
     journal = {The electronic journal of linear algebra},
     pages = {34--43},
     publisher = {mathdoc},
     volume = {1},
     year = {1996},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_1996__1__a3/}
}
TY  - JOUR
AU  - Fricke, Gerd H.
AU  - Hedetniemi, Stephen T.
AU  - Jacobs, David P.
AU  - Trevisan, Vilmar
TI  - Reducing the adjacency matrix of a tree
JO  - The electronic journal of linear algebra
PY  - 1996
SP  - 34
EP  - 43
VL  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_1996__1__a3/
LA  - en
ID  - ELA_1996__1__a3
ER  - 
%0 Journal Article
%A Fricke, Gerd H.
%A Hedetniemi, Stephen T.
%A Jacobs, David P.
%A Trevisan, Vilmar
%T Reducing the adjacency matrix of a tree
%J The electronic journal of linear algebra
%D 1996
%P 34-43
%V 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_1996__1__a3/
%G en
%F ELA_1996__1__a3
Fricke, Gerd H.; Hedetniemi, Stephen T.; Jacobs, David P.; Trevisan, Vilmar. Reducing the adjacency matrix of a tree. The electronic journal of linear algebra, Tome 1 (1996), pp. 34-43. http://geodesic.mathdoc.fr/item/ELA_1996__1__a3/