Distance Integral Complete $r$-Partite Graphs

Ruosong Yang, Ligong Wang

Let $D(G)=(d_{ij})_{n\times n}$ denote the distance matrix of a connected graph $G$ with order $n$, where $d_{ij}$ is equal to the distance between vertices $v_i$ and $v_j$ in $G$. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In this paper, we investigate distance integral complete $r$-partite graphs $K_{p_1,p_2,\ldots,p_r}=K_{a_1\cdot p_1,a_2\cdot p_2,\ldots,a_s\cdot p_s}$ and give a sufficient and necessary condition for $K_{a_1\cdot p_1,a_2\cdot p_2,\ldots,a_s\cdot p_s}$ to be distance integral, from which we construct infinitely many new classes of distance integral graphs with $s=1,2,3,4$. Finally, we propose two basic open problems for further study.