Uniform supertrees with extremal spectral radii

Abstract

A supertree is a connected and acyclic hypergraph. We investigate the supertrees with the extremal spectral radii among several kinds of r-uniform supertrees. First, by using the matching polynomials of supertrees, a new and useful grafting operation is proposed for comparing the spectral radii of supertrees, and its applications are shown to obtain the supertrees with the extremal spectral radii among some kinds of r-uniform supertrees. Second, the supertree with the third smallest spectral radius among the r-uniform supertrees is deduced. Third, among the r-uniform supertrees with a given maximum degree, the supertree with the smallest spectral radius is derived. At last, among the r-uniform starlike supertrees, the supertrees with the smallest and the largest spectral radii are characterized.

Keywords

Hypergraph / spectral radius / supertree / matching polynomial

References

[1] Clark G J, Cooper J N. On the adjacency spectra of hypertrees. Electron J Combin, 2018, 25: P2.48

[2] Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl, 2012, 436: 3268–3292

[3] Fan Y Z, Tan Y Y, Peng X X, Liu A H. Maximizing spectral radii of uniform hyper-graphs with few edges. Discuss Math Graph Theory, 2016, 36: 845–856

[4] Guo H Y, Zhou B. On the spectral radius of uniform hypertrees. Linear Algebra Appl, 2018, 558: 236–249

[5] Hu S L, Qi L Q, Shao J Y. Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues. Linear Algebra Appl, 2013, 439: 2980–2998

[6] Khan M U, Fan Y Z. On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs. Linear Algebra Appl, 2015, 480: 93–106

[7] Li H H, Shao J Y, Qi L Q. The extremal spectral radii of k-uniform supertrees. J Comb Optim, 2016, 32: 741–764

[8] Li W, Michael K N. Some bounds for the spectral radius of nonnegative tensors. Numer Math, 2015, 130(2): 315–335

[9] Lim L H. Singular values and eigenvalues of tensors: a variational approach. In: Proc the 1st IEEE Intl Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP'05. 2005, 129–132

[10] Lovász L, Pelikán J. On the eigenvalues of trees. Period Math Hungar, 1973, 3: 175–182

[11] Lv C, You L H, Zhang X D. A sharp upper bound on the spectral radius of a non-negative k-uniform tensor and its applications to (directed) hypergraphs. J Inequal Appl, 2020, 32: 1–16

[12] Ouyang C, Qi L Q, Yuan X Y. The first few unicyclic and bicyclic hypergraphs with largest spectral radii. Linear Algebra Appl, 2017, 527: 141–162

[13] Qi L Q. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324

[14] Su L, Kang L Y, Li H H, Shan E F. The matching polynomials and spectral radii of uniform supertrees. Electron J Combin, 2018, 25: P4.13

[15] Su L, Kang L Y, Li H H, Shan E F. The largest spectral radius of uniform hypertrees with a given size of matching. Linear Multilinear Algebra, 2020, 68: 1779–1791

[16] Wang W H. The minimal spectral radius of the r-uniform supertree having two vertices of maximum degree. Linear Multilinear Algebra, doi.org/10.1080/03081087.2020.1819188

[17] Xiao P, Wang L G. The maximum spectral radius of uniform hypergraphs with given number of pendant edges. Linear Multilinear Algebra, 2019, 67: 1392–1403

[18] Xiao P, Wang L G, Du Y F. The first two largest spectral radii of uniform supertrees with given diameter. Linear Algebra Appl, 2018, 536: 103–119

[19] Xiao P, Wang L G, Lu Y. The maximum spectral radii of uniform supertrees with given degree sequences. Linear Algebra Appl, 2017, 523: 33–45

[20] You L H, Huang X H, Yuan X Y. Sharp bounds for spectral radius of nonnegative weakly irreducible tensors. Front Math China, 2019, 14: 989–1015

[21] Yuan X Y, Shao J Y, Shan H Y. Ordering of some uniform supertrees with larger spectral radii. Linear Algebra Appl, 2016, 495: 206–222

[22] Yuan X Y, Zhang M, Lu M. Some upper bounds on the eigenvalues of uniform hyper-graphs. Linear Algebra Appl, 2015, 484: 540–549

[23] Zhang J B, Li J P. The maximum spectral radius of k-uniform hypergraphs with r pendent vertices. Linear Multilinear Algebra, 2019, 67: 1062–1073

[24] Zhang L, Chang A. Spectral radius of r-uniform supertrees with perfect matchings. Front Math China, 2018, 13: 1489{1499

[25] Zhang W, Kang L Y, Shan E F, Bai Y Q. The spectra of uniform hypertrees. Linear Algebra Appl, 2017, 533: 84–94

RIGHTS & PERMISSIONS

Higher Education Press