×

Distance matrix and Laplacian of a tree with attached graphs. (English) Zbl 1075.05052

Summary: 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A09 Theory of matrix inversion and generalized inverses
15A15 Determinants, permanents, traces, other special matrix functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bapat, R. B., Resistance distance in graphs, Math. Student, 68, 87-98 (1999) · Zbl 1194.05031
[2] Bapat, R. B., Resistance matrix of a weighted graph, MATCH Commun. Math. Comput. Chem., 50, 73-82 (2004) · Zbl 1052.05028
[3] Bapat, R. B.; Grossman, J. W.; Kulkarni, D. M., Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra, 46, 299-312 (1999) · Zbl 0940.05042
[4] Bapat, R. B.; Kulkarni, D. M., Minors of some matrices associated with a tree, (Huynh, D. V.; Jain, S. K.; Lopez-Permouth, S. R., in: Algebra and its Applications. in: Algebra and its Applications, Contemporary Mathematics, vol. 259 (2000), American Math Society), 45-66 · Zbl 0979.05075
[5] R.B. Bapat, S.J. Kirkland, M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl., in press (doi:10.1016/j.laa.2004.05.011; R.B. Bapat, S.J. Kirkland, M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl., in press (doi:10.1016/j.laa.2004.05.011 · Zbl 1064.05097
[6] Bapat, R. B.; Raghavan, T. E.S., Nonnegative Matrices and Applications, (Encyclopedia of Mathematics and its Applications, vol. 64 (1997), Cambridge University Press) · Zbl 0879.15015
[7] Ben-Israel, A.; Greville, T. N.E., Generalized Inverses: Theory and Applications (1974), Wiley-Interscience · Zbl 0305.15001
[8] Bollobás, B., Modern Graph Theory (1998), Springer-Verlag: Springer-Verlag New York · Zbl 0902.05016
[9] Campbell, S. L.; Meyer, C. D., Generalized Inverses of Linear Transformations (1979), Pitman · Zbl 0417.15002
[10] Chaiken, S., A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods, 3, 319-329 (1982) · Zbl 0495.05018
[11] Doyle, P. G.; Snell, J. L., Random Walks and Electrical Networks (1984), Math. Assoc. Am.: Math. Assoc. Am. Washington · Zbl 0583.60065
[12] Fiedler, M., Aggregation in graphs, Colloq. Math. Soc. J́anos Bolyai, 18, 315-330 (1978) · Zbl 0384.05053
[13] Graham, R. L.; Pollack, H. O., On the addressing problem for loop switching, Bell System Tech. J., 50, 2495-2519 (1971) · Zbl 0228.94020
[14] Graham, R. L.; Lovász, L., Distance matrix polynomials of trees, Adv. in Math., 29, 1, 60-88 (1978) · Zbl 0382.05023
[15] Kaplan, E. L., Mathematical Programming and Games (1982), John Wiley · Zbl 0483.90058
[16] Klein, D. J., Graph geometry, graph metrics and Weiner, MATCH Commun. Math. Comput. Chem., 35, 7-27 (1997) · Zbl 1014.05063
[17] Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993)
[18] Mayeda, W., Graph Theory (1972), Wiley-Interscience · Zbl 0111.32104
[19] Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197,198, 143-176 (1994) · Zbl 0802.05053
[20] Rao, C. R., Linear Statistical Inference and its Applications (1973), John Wiley: John Wiley New York · Zbl 0169.21302
[21] Reid, L.; Sun, X., Distance matrices and ridge function interpolation, Can. J. Math., 45, 6, 1313-1323 (1993) · Zbl 0793.41007
[22] Sun, X., Solvability of multivariate interpolation by radial or related functions, J. Approx. Theory, 72, 3, 252-267 (1993) · Zbl 0785.41002
[23] Schrijver, A., Theory of Linear and Integer Programming (1986), John Wiley · Zbl 0665.90063
[24] West, D. B., Introduction to Graph Theory (2001), Prentice-Hall Inc.
[25] Xiao, W.; Gutman, I., On resistance matrices, MATCH Commun. Math. Comput. Chem., 49, 67-81 (2003) · Zbl 1049.05053
[26] Xiao, W.; Gutman, I., Resistance distance and Laplacian spectrum, Theor. Chem. Acc., 110, 284-289 (2003)
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.