论文标题
双线性矩阵方程的特征是加权树的laplacian和距离矩阵
Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees
论文作者
论文摘要
从代数图理论中可以知道，如果$ l $是某些树$ g $的laplacian矩阵，则带有顶点度序列$ \ mathbf {d} =（d_1，...，...，d_n）^\ top $，$ d $是其距离矩阵，然后$ LD+2i =（2 \ CDOT \ MATHBF {1} - \ MATHBF {d}）\ MATHBF {1}^\ top $，其中$ \ Mathbf {1} $是全部列向量。我们证明，如果此矩阵身份适用于某些图$ g $的拉普拉斯矩阵，其中具有度序列$ \ mathbf {d} $，而对于某些矩阵$ d $，则$ g $本质上是一棵树，而$ d $是其距离矩阵。该结果立即将其推广到加权图。如果矩阵$ d $是对称的，则该矩阵身份的下三角部分是多余的，可以省略。因此，上述双线矩阵方程在$ l $，$ d $和$ \ mathbf {d} $中以其laplacian和远程矩阵来表征树。讨论了对极端图理论的应用（特别是，拓扑指数优化和最佳树问题）和道路拓扑设计。
It is known from the algebraic graph theory that if $L$ is the Laplacian matrix of some tree $G$ with a vertex degree sequence $\mathbf{d}=(d_1, ..., d_n)^\top$ and $D$ is its distance matrix, then $LD+2I=(2\cdot\mathbf{1}-\mathbf{d})\mathbf{1}^\top$, where $\mathbf{1}$ 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 $\mathbf{d}$ 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 $\mathbf{d}$ 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.
