66372

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees

Электронная публикация: 

Да

ISBN/ISSN: 

0166-218X

DOI: 

10.1016/j.dam.2021.08.025

Наименование источника: 

  • Discrete Applied Mathematics

Обозначение и номер тома: 

V. 305

Город: 

  • Amsterdam

Издательство: 

  • Elsevier

Год издания: 

2021

Страницы: 

1-9
Аннотация
It is known from algebraic graph theory that if L is the Laplacian matrix of some tree G with a vertex degree sequence $\vec{d}=(\delta_1, ..., \delta_n)^\top$ and D is its distance matrix, then $LD+2I=(2\cdot\vec{1}-\vec{d})\vec{1}^\top$, where $\vec{1}$ is an all-ones column vector. We prove the converse proposition: if this identity holds for the Laplacian matrix of some graph G with a degree sequence $\vec{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. Therefore, the above bilinear matrix equation in L, D, and $\vec{d}$ characterizes trees in terms of their Laplacian and distance matrices, so it can be used as a constraint in mixed-integer formulations of distance-related tree topology design problems (e.g., optimum communication spanning tree or hop-constrained minimum spanning tree problems). If the matrix D is symmetric, the lower triangular part of this matrix identity is redundant and can be omitted, which halves the number of constraints in an optimization problem. Applications to the extremal graph theory (especially, to topological index optimization and to optimal tree problems) and to road topology design are discussed.

Библиографическая ссылка: 

Губко М.В., Веремьев А.Ф. Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees // Discrete Applied Mathematics. 2021. V. 305. С. 1-9.