Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees

preprint2021arXivOpen access

Abstract

It is known from the algebraic graph theory that if LL is the Laplacian matrix of some tree GG with a vertex degree sequence d=(d1,...,dn)⊤\mathbf{d}=(d_1, ..., d_n)^\top and DD is its distance matrix, then LD+2I=(2⋅1−d)1⊤LD+2I=(2\cdot\mathbf{1}-\mathbf{d})\mathbf{1}^\top, where 1\mathbf{1} is an all-ones column vector. We prove that if this matrix identity holds for the Laplacian matrix of some graph GG with a degree sequence d\mathbf{d} and for some matrix DD, then GG is essentially a tree, and DD is its distance matrix. This result immediately generalizes to weighted graphs. If the matrix DD is symmetric, the lower triangular part of this matrix identity is redundant and can be omitted. Therefore, the above bilinear matrix equation in LL, DD, and d\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.