The Laplacian of a uniform hypergraph

Shenglong Hu, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

45 Citations (Scopus)

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 languageEnglish
Pages (from-to)331-366
Number of pages36
JournalJournal of Combinatorial Optimization
Volume29
Issue number2
DOIs
Publication statusPublished - 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

Cite this