Largest H-eigenvalue of uniform s-hypertrees

Abstract

The k-uniform s-hypertree G = (V,E) is an s-hypergraph, where 1≤s≤k −1, and there exists a host tree T with vertex set V such that each edge of G induces a connected subtree of T. In this paper, some properties of uniform s-hypertrees are establised, as well as the upper and lower bounds on the largest H-eigenvalue of the adjacency tensor of k-uniform s-hypertrees in terms of the maximal degree Δ. Moreover, we also show that the gap between the maximum and the minimum values of the largest H-eigenvalue of k-uniform s-hypertrees is just Θ(Δ^s/k).

Keywords

Largest H-eigenvalue / spectral radius / adjacency tensor / hypertree

References

[1] Berge C. Hypergraph: Combinatorics of Finite Sets.Amsterdam: North-Holland, 1989

[2] Bretto A. Hypergraph Theory: An Introduction.Berlin: Springer, 2013

[3] Brandstädt A, Dragan F, Chepoi V, Voloshin V. Dually chordal graphs. SIAM J Discrete Math, 1998, 11: 437–455

[4] Chang K, Pearson K, Zhang T. Perron-Frobenius theorem for nonnegative tensors. Commun Math Sci, 2008, 6: 507–520

[5] Chang K, Qi L, Zhang T. A survey on the spectral theory of nonnegative tensors. Numer Linear Algebra Appl, 2013, 20: 891–912

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

[7] Friedland S, Gaubert A, Han L. Perron-Frobenius theorems for nonnegative multilinear forms and extensions. Linear Algebra Appl, 2013, 438: 738–749

[8] Hardy G, Littlewood J, Pólya G. Inequalities.2nd ed. Cambridge: Cambridge Univ Press, 1988

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

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

[11] Lim L. Singular values and eigenvalues of tensors: a variational approach. In: Proc of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 05). 2005, 129–132

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

[13] Qi L, Shao J, Wang Q. Regular uniform hypergraphs, s-cycles, s-paths and their largest Laplacian H-eigenvalues. Linear Algebra Appl, 2014, 443: 215–227

[14] Stevanovi´c D. Bounding the largest eigenvalue of trees in terms of the largest vertex degree. Linear Algebra Appl, 2003, 360: 35–42

[15] Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J Matrix Anal Appl, 2010, 31: 2517–2530

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature