2015/07/07 by Mikhail Goubko, Goubko, Mikhail
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Topological and Geometric Data Analysis #math.CO
paper · pdf · doi:10.48550/arxiv.1507.01733
21 pages, 5 figures
openalex publication_date 2015/07/07 · arxiv created 2015/07/08 · arxiv updated 2015/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a tree with the given sequence of vertex degrees the spectral radius of its terminal distance matrix is shown to be bounded from below by the the average row sum of the terminal distance matrix of the, so called, BFS-tree (also known as a greedy tree). This lower bound is typically not tight; nevertheless, since spectral radius of the terminal distance matrix of BFS-tree is a natural upper bound, the numeric simulation shows that relative gap between the upper and the lower bound does not exceed 3% (we also make a step towards justifying this fact analytically.) Therefore, the conjecture that BFS-tree has the minimum terminal distance spectral radius among all trees with the given degree sequence is valid with accuracy at least 97%. The same technique can be applied to the distance spectral radius of trees, which is a more popular topological index.