Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees

DOI10.1016/J.DAM.2021.08.025MaRDI QIDQ2235240zbMATH OpenOpenAlexFDO

Authors Mikhail Goubko, Alexander Veremyev

Publication date 21 October 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.06068

zbMATH Keywords

extremal graph theorymatrix equationmixed-integer programmingoptimal tree problemWiener index

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrix equations and identities (15A24) Mixed integer programming (90C11)

Abstract: It is known from the algebraic graph theory that if $L$ is the Laplacian matrix of some tree $G$ with a vertex degree sequence $mathbfd=(d_1,\mathrm{...},d_n{)}^{o}p$ and $D$ is its distance matrix, then $LD+2I=(2cdotmathbf1-mathbfd)mathbf{1}^{o}p$, where $mathbf1$ is an all-ones column vector. We prove that if this matrix identity holds for the Laplacian matrix of some graph $G$ with a degree sequence $mathbfd$ and for some matrix $D$, then $G$ is essentially a tree, and $D$ is its distance matrix. This result immediately generalizes to weighted graphs. If the matrix $D$ is symmetric, the lower triangular part of this matrix identity is redundant and can be omitted. Therefore, the above bilinear matrix equation in $L$, $D$, and $mathbfd$ characterizes trees in terms of their Laplacian and distance matrices. Applications to the extremal graph theory (especially, to topological index optimization and to optimal tree problems) and to road topology design are discussed.

Recommendations

• On distance and Laplacian matrices of trees with matrix weights
• scientific article; zbMATH DE number 5005342
• Trees with matrix weights: Laplacian matrix and characteristic-like vertices
• Squared distance matrices of trees with matrix weights
• Distances in Weighted Trees and Group Inverse of Laplacian Matrices
• Determinant of the distance matrix of a tree with matrix weights
• Distance matrix and Laplacian of a tree with attached graphs
• The bipartite Laplacian matrix of a nonsingular tree
• Squared distance matrix of a weighted tree
• The bipartite distance matrix of a nonsingular tree

Cites work

• A polyhedral study of the diameter constrained minimum spanning tree problem
• A survey on graphs extremal with respect to distance-based topological indices
• Block distance matrices
• Bounding the k-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• Degree-based topological indices: optimal trees with given number of pendents
• Distance matrix polynomials of trees
• Generalized inverse of the Laplacian matrix and some applications
• Graphs with a given diameter that maximise the Wiener index
• scientific article; zbMATH DE number 2121250 (Why is no real title available?)
• Lower bound for the cost of connecting tree with given vertex degree sequence
• Maximizing Wiener index for trees with given vertex weight and degree sequences
• Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences
• Multicommodity flow models for spanning trees with hop constraints
• New formulations and solution procedures for the hop constrained network design problem.
• Note on minimizing degree-based topological indices of trees with given number of pendent vertices
• On distance matrices and Laplacians
• On Euclidean distance matrices
• On the Addressing Problem for Loop Switching
• Optimum Communication Spanning Trees
• Properties of Euclidean and non-Euclidean distance matrices
• Squared distance matrix of a tree: inverse and inertia
• Sum of weighted distances in trees

Cited in

(4)

• Trees with matrix weights: Laplacian matrix and characteristic-like vertices
• scientific article; zbMATH DE number 5005342 (Why is no real title available?)
• Distances in Weighted Trees and Group Inverse of Laplacian Matrices
• On distance and Laplacian matrices of trees with matrix weights

This page was built for publication: Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees

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