𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distance matrix and Laplacian of a tree with attached graphs

✍ Scribed by R.B. Bapat

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
172 KB
Volume
411
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

A tree with attached graphs is a tree, together with graphs defined on its partite sets. We introduce the notion of incidence matrix, Laplacian and distance matrix for a tree with attached graphs. Formulas are obtained for the minors of the incidence matrix and the Laplacian, and for the inverse and the determinant of the distance matrix. The case when the attached graphs themselves are trees is studied more closely. Several known results, including the Matrix Tree theorem, are special cases when the tree is a star. The case when the attached graphs are paths is also of interest since it is related to the transportation problem.

πŸ“œ SIMILAR VOLUMES

Permanent of the Laplacian matrix of tre
Permanent of the Laplacian matrix of trees and bipartite graphs
✍ Richard A Brualdi; John L Goldwasser πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 805 KB

be the Laplacian matrix of G. When G is a tree or a bipartite graph we obtain bounds for the permanent of L(G) both in terms of n only and in terms of d 1 ..... d,. Improved bounds are obtained in terms of the diameter of T and the size of a matching in T.

Permanent of the laplacian matrix of tre
Permanent of the laplacian matrix of trees with a given matching
✍ John L Goldwasser πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 715 KB

We define the Laplacian ratio of a tree z(T), to be the permanent of the Laplacian matrix of T divided by the product of the degrees of the vertices. Best possible lower and upper bounds are obtained for ~r(T) in terms of the size of the largest matching in T.

Bounding the diameter and the mean dista
Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods
✍ J.A. RodrΓ­guez; J.L.A. Yebra πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 527 KB

Recently, several results bounding above the diameter and/or the mean distance of a graph from its eigenvalues have been presented. They use the eigenvalues of either the adjacency or the Laplacian matrix of the graph. The main object of this paper is to compare both methods. As expected, they are e