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.

Key words： 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