Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices

Abstract

Let G be a connected hypergraph with even uniformity, which contains cut vertices. Then G is the coalescence of two nontrivial connected sub-hypergraphs (called branches) at a cut vertex. Let \mathcal{A}(G) be the adjacency tensor of G. The least H-eigenvalue of \mathcal{A}(G) refers to the least real eigenvalue of \mathcal{A}(G) associated with a real eigenvector. In this paper, we obtain a perturbation result on the least H-eigenvalue of \mathcal{A}(G) when a branch of G attached at one vertex is relocated to another vertex, and characterize the unique hypergraph whose least H-eigenvalue attains the minimum among all hypergraphs in a certain class of hypergraphs which contain a fixed connected hypergraph.

Key words： Hypergraph; adjacency tensor; least H-eigenvalue; eigenvector; perturbation

References

1 Berge C. Hypergraphs: Combinatorics of Finite Sets. Amsterdam: North-Holland, 1989

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

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

4 Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl, 2012, 436(9): 3268–3292

5 Fan Y Z, Bao Y H, Huang T. Eigenvariety of nonnegative symmetric weakly irreducible tensors associated with spectral radius and its application to hypergraphs. Linear Algebra Appl, 2019, 564: 72–94

6 Fan Y Z, Huang T, Bao Y H, Zhuan-Sun C L, Li Y P. The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs. Trans Amer Math Soc, 2019, 372(3): 2213–2233

7 Fan Y Z, Khan M, Tan Y Y. The largest H-eigenvalue and spectral radius of Laplacian tensor of non-odd-bipartite generalized power hypergraphs. Linear Algebra Appl, 2016, 504: 487–502

8 Fan Y Z, Tan Y Y, Peng X X, Liu A H. Maximizing spectral radii of uniform hypergraphs with few edges. Discuss Math Graph Theory, 2016, 36: 845–856

9 Fan Y Z, Wang Y, Bao Y H, Wan J C, Li M, Zhu Z. Eigenvectors of Laplacian or signless Laplacian of hypergraphs associated with zero eigenvalue. Linear Algebra Appl, 2019, 579: 244–261

10 Fan Y Z, Wang Y, Gao Y B. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread. Linear Algebra Appl, 2008, 429: 577–588

11 Friedland S, Gaubert S, Han L. Perron-Frobenius theorem for nonnegative multilinear forms and extensions. Linear Algebra Appl, 2013, 438: 738–749

12 Hu S, Qi L. The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph. Discrete Appl Math, 2014, 169: 140–151

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

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

15 Khan M, Fan Y Z, Tan Y Y. The H-spectra of a class of generalized power hypergraphs. Discrete Math, 2016, 339: 1682–1689

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

17 Lim L H. Singular values and eigenvalues of tensors: a variational approach. Proceedings of the 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005, 129–132

18 Lu L, Man S. Connected hypergraphs with small spectral radius. Linear Algebra Appl, 2016, 509: 206–227

19 Nikiforov V. Hypergraphs and hypermatrices with symmetric spectrum. Linear Algebra Appl, 2017, 519: 1–18

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

21 Shao J Y, Shan H Y, Wu B F. Some spectral properties and characterizations of connected odd-bipartite uniform hypergraphs. Linear Multilinear Algebra, 2015, 63: 2359–2372

22 Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J Matrix Anal Appl, 2010, 31(5): 2517–2530

23 Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonnegative tensors II. SIAM J Matrix Anal Appl, 2011, 32(4): 1236–1250

24 Yang Y, Yang Q. On some properties of nonnegative weakly irreducible tensors. arXiv: 1111.0713v2