Trees with given maximum degree minimizing the spectral radius

Xu Du Beijing Jiaotong University Lingsheng Shi Tsinghua University

Combinatorics mathscidoc:1611.06001

Electronic Journal of Linear Algebra, 31, 335-361, 2016
The spectral radius of a graph is the largest eigenvalue of the adjacency matrix of the graph. Let T(n,D l) be the tree which minimizes the spectral radius of all trees of order n with exactly l vertices of maximum degree D. In this paper, T(n,D l) is determined for D=3, and for l<= 3 and n large enough. It is proven that for sufficiently large n, T(n, 3, l) is a caterpillar with (almost) uniformly distributed legs, T(n,D 2) is a dumbbell, and T(n,D,3) is a tree consisting of three distinct stars of order D connected by three disjoint paths of (almost) equal length from their centers to a common vertex. The unique tree with the largest spectral radius among all such trees is also determined. These extend earlier results of Lov´asz and Pelik´an, Simi´c and To˘si´c, Wu, Yuan and Xiao, and Xu, Lin and Shu.
No keywords uploaded!
[ Download ] [ 2016-11-24 11:07:41 uploaded by lshi ] [ 1312 downloads ] [ 0 comments ]
@inproceedings{xu2016trees,
  title={Trees with given maximum degree minimizing the spectral radius},
  author={Xu Du, and Lingsheng Shi},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161124110741998761636},
  booktitle={Electronic Journal of Linear Algebra},
  volume={31},
  pages={335-361},
  year={2016},
}
Xu Du, and Lingsheng Shi. Trees with given maximum degree minimizing the spectral radius. 2016. Vol. 31. In Electronic Journal of Linear Algebra. pp.335-361. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161124110741998761636.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved