×

On distance matrices and Laplacians. (English) Zbl 1064.05097

The distance matrix \(D\) of a graph \(G\) of order \(n\) is the \(n\times n\) matrix with zeroes on the diagonal where the entries represent distances between pairs of vertices of \(G\). The authors extend a previous result for unweighted trees of R. L. Graham and L. Lovász [Adv. Math. 29, 60–88 (1978; Zbl 0382.05023)] and provide a formula for the determinant and the inverse matrix of the distance matrix of weighted trees and unweighted unicyclic graphs. At the end of the paper, the obtained results are used to compute determinants of \(L_1\)-distance matrices of certain special sets of points in the plane.
The authors also consider Laplacians of graphs. The {Laplacian} of a graph \(H\) is the matrix whose entries on the diagonal are equal to the sum of the weights of the edges incident with corresponding vertices and the remaining entries are equal to the negative square roots of the weights of the edges. The authors obtain the following surprising result: if \(D\) is the distance matrix of a weighted tree and \(L\) is the Laplacian matrix of an arbitrary weighted graph, then \((D^{-1}-L)^{-1}\) is an entry-wise positive matrix.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Citations:

Zbl 0382.05023
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bapat, R. B., The Laplacian matrix of a graph, Math. Student, 65, 214-223 (1996) · Zbl 1194.05079
[2] Dyn, N.; Light, W. A.; Cheney, E. W., Interpolation by piecewise-linear radial basis functions I, J. Approx. Theory, 59, 202-223 (1989) · Zbl 0678.41001
[3] Graham, R. L.; Pollack, H. O., On the addressing problem for loop switching, Bell System Tech. J., 50, 2495-2519 (1971) · Zbl 0228.94020
[4] Graham, R. L.; Lovász, L., Distance matrix polynomials of trees, Adv. Math., 29, 1, 60-88 (1978) · Zbl 0382.05023
[5] Kaplan, Edward J., Mathematical Programming and Games (1982.), John Wiley
[6] Merris, R., The distance spectrum of a tree, J. Graph Theory, 14, 3, 365-369 (1990) · Zbl 0734.05037
[7] Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197/198, 143-176 (1994) · Zbl 0802.05053
[8] Parthasarathy, T.; Ravindran, G., N-matrices, Linear Algebra Appl., 139, 89-102 (1990) · Zbl 0719.15010
[9] Reid, L.; Sun, X., Distance matrices and ridge function interpolation, Can. J. Math., 45, 6, 1313-1323 (1993) · Zbl 0793.41007
[10] Sun, X., Solvability of multivariate interpolation by radial or related functions, J. Approx. Theory, 72, 3, 252-267 (1993) · Zbl 0785.41002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.