On the Spectrum of the Line Graph of a Family of Bipartite Graphs Arising from the Boolean Lattice

Abstract

The Boolean lattice $B{L}_n$, $n\ge 3$, is the graph whose vertex set is the collection of all subsets of $[n]=\{1,2,\dots ,n\}$, where two subsets $U$ and $W$ are adjacent if and only if their symmetric difference has precisely one element. In the graph $B{L}_n$, the \emph{layer} $L_k$ is the family of all $k$-element subsets of $[n]$. The subgraph $B{L}_n(k-1,k)$ is the induced subgraph of $B{L}_n$ on layers $L_{k-1}$ and $L_k$. This graph is bipartite and, when $n=2k-1$, is $k$-regular and isomorphic to the bipartite double cover $2\cdot O_k$ of the odd graph $O_k$. In this paper, we determine the full adjacency spectrum -- eigenvalues together with their multiplicities -- of the line graph $L(B{L}_n(k-1,k))$ for all admissible values of $n$ and $k$. As a consequence, we show that $L(B{L}_n(k-1,k))$ is an integral graph whenever $n=2k-1$, and we recover as a special case the spectrum of the line graph $L(n)$ of $B{L}_n(1,2)$ established by Mirafzal~\cite{pap-sm-1}.

13 pages