Abstract
In this paper, we investigate the Laplacian, i.e., the normalized Laplacian tensor of a k-uniform hypergraph. We show that the real parts of all the eigenvalues of the Laplacian are in the interval [0,2], and the real part is zero (respectively two) if and only if the eigenvalue is zero (respectively two). All the H+-eigenvalues of the Laplacian and all the smallest H+-eigenvalues of its sub-tensors are characterized through the spectral radii of some nonnegative tensors. All the H+-eigenvalues of the Laplacian that are less than one are completely characterized by the spectral components of the hypergraph and vice verse. The smallest H-eigenvalue, which is also an H+-eigenvalue, of the Laplacian is zero. When k is even, necessary and sufficient conditions for the largest H-eigenvalue of the Laplacian being two are given. If k is odd, then its largest H-eigenvalue is always strictly less than two. The largest H+-eigenvalue of the Laplacian for a hypergraph having at least one edge is one; and its nonnegative eigenvectors are in one to one correspondence with the flower hearts of the hypergraph. The second smallest H+-eigenvalue of the Laplacian is positive if and only if the hypergraph is connected. The number of connected components of a hypergraph is determined by the H+-geometric multiplicity of the zero H+-eigenvalue of the Lapalacian.
Original language | English |
---|---|
Pages (from-to) | 331-366 |
Number of pages | 36 |
Journal | Journal of Combinatorial Optimization |
Volume | 29 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 2013 |
Keywords
- Eigenvalue
- Hypergraph
- Laplacian
- Tensor
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics