Line Multigraphs of General Hypergraphs

Abstract

A line multigraph is obtained from a hypergraph by taking its hyperedges as vertices and joining two of them by as many edges as the number of vertices they share. We develop a matrix theory for line multigraphs of general, not necessarily uniform, hypergraphs. The central tool is the identity ${\mathbf{B}}^{\mathrm{T}}\mathbf{B}=\mathbf{C}+{\mathbf{A}}_{\mathcal{L}}$, where $\mathbf{B}$ is the incidence matrix, $\mathbf{C}$ is the diagonal matrix of hyperedge cardinalities and ${\mathbf{A}}_{\mathcal{L}}$ is the adjacency matrix of the line multigtaph. From this identity, we prove that the eigenvalues of the line multigraph of a hypergraph of rank $r$ are at least $-r$, and we describe the eigenspace and the multiplicity of $-r$ through an essential core of the hypergraph. We also give an explicit combinatorial condition under which $-r$ is attained. As applications, we bound the spectral radius of the signless Laplacian matrix, characterizing the cases of equality, and we determine the complete signless Laplacian spectrum of a general power hypergraph. On the structural side, we show that connectivity, linearity, and regularity transfer between a hypergraph and its line multigraph, that every hypergraph shares its line multigraph with infinitely many others, and that each class of such hypergraphs contains a reduced representative.

arXiv comment19 pages, 2 figures. Revised version: The theory is extended from uniform to general hypergraphs, with new results on the eigenspace and multiplicity of the smallest eigenvalue, collars, and a line-equivalence relation between hypergraphs