Diameter minimal trees

被引:7
|
作者
Johnson, Charles R. [1 ]
Saiago, Carlos M. [2 ]
机构
[1] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA
[2] Univ Nova Lisboa, Dept Matemat, Fac Ciencias & Tecnol, Quinta Da Torre, Portugal
关键词
branch duplication; diameter; distinct eigenvalues; Hermitian matrix; multiplicities; tree; EIGENVALUES; GRAPH; MATRICES;
D O I
10.1080/03081087.2015.1057097
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Using the method of seeds and branch duplication, it is shown that for every tree of diameter d < 7, there is an Hermitian matrix with as few as d distinct eigenvalues (a known lower bound). For diameter 7, some trees require 8 distinct eigenvalues, but no more; the seeds for which 7 and 8 are the worst case are classified. For trees of diameter d, it is shown that, in general, the minimum number of distinct eigenvalues is bounded by a function of d. Many trees of high diameter permit as few of distinct eigenvalues as the diameter and a conjecture is made that all linear trees are of this type. Several other specific, related observations are made.
引用
收藏
页码:557 / 571
页数:15
相关论文
共 50 条
  • [1] The minimal Laplacian spectral radius of trees with diameter 4
    Zhang, Haixia
    Wang, Yi
    THEORETICAL COMPUTER SCIENCE, 2017, 657 : 191 - 195
  • [2] On minimal energies of trees of a prescribed diameter
    Zhou, Bo
    Li, Feng
    JOURNAL OF MATHEMATICAL CHEMISTRY, 2006, 39 (3-4) : 465 - 473
  • [3] On minimal energies of trees with given diameter
    Li, Shuchao
    Li, Nana
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2008, 17 : 414 - 425
  • [4] On minimal energies of trees of a prescribed diameter
    Bo Zhou
    Feng Li
    Journal of Mathematical Chemistry, 2006, 39 : 465 - 473
  • [5] Minimal Energy Trees of Given Bipartition and Diameter
    Liu, Zhongzhu
    Zhou, Bo
    UTILITAS MATHEMATICA, 2012, 89 : 3 - 13
  • [6] The minimal Laplacian spectral radius of trees with a given diameter
    Liu, Ruifang
    Lu, Zhonghua
    Shu, Jinlong
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 78 - 83
  • [7] The minimal Randic energy of trees with given diameter
    Gao, Yubin
    Gao, Wei
    Shao, Yanling
    APPLIED MATHEMATICS AND COMPUTATION, 2021, 411
  • [8] Trees with minimal index and diameter at most four
    Belardo, Francesco
    Li Marzi, Enzo M.
    Simic, Slobodan K.
    DISCRETE MATHEMATICS, 2010, 310 (12) : 1708 - 1714
  • [9] INDICES OF TREES WITH A PRESCRIBED DIAMETER
    Simic, Slobodan K.
    Zhou, Bo
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2007, 1 (02) : 446 - 454
  • [10] The number of subtrees of trees with given diameter
    Chen, Zichong
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (01)