2020/08/13 by Mikhail Goubko, Goubko, Mikhail, Alexander Veremyev +1
Computer Science · Mathematics · #05C05 #05C12 #05C35 #05C50 #15A24 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #G.1.6 #G.2.2 #Graph theory and applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2008.06068
openalex publication_date 2020/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known from the algebraic graph theory that if L is the Laplacian\nmatrix of some tree G with a vertex degree sequence \d=(d1, ...,\ndn)^ top and D is its distance matrix, then\nLD+2I=(2\⋅\1-\d)\1^ top, where \1 is an\nall-ones column vector. We prove that if this matrix identity holds for the\nLaplacian matrix of some graph G with a degree sequence \d and for\nsome matrix D, then G is essentially a tree, and D is its distance\nmatrix. This result immediately generalizes to weighted graphs. If the matrix\nD is symmetric, the lower triangular part of this matrix identity is\nredundant and can be omitted. Therefore, the above bilinear matrix equation in\nL, D, and \d characterizes trees in terms of their Laplacian and\ndistance matrices. Applications to the extremal graph theory (especially, to\ntopological index optimization and to optimal tree problems) and to road\ntopology design are discussed.\n