On middle cube graphs

C. Dalfo (Departament de Matematica Aplicada IV, Universitat Politecnica de Catalunya)
M. A. Fiol (Departament de Matematica Aplicada IV, Universitat Politecnica de Catalunya)
M. Mitjana (Departament de Matematica Aplicada I, Universitat Politecnica de Catalunya)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 3, No 2 (2015): Electronic Journal of Graph Theory and Applications

We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors).