Integral Complete Multipartite Graphs

Ligong Wang 1 and Xiaodong Liu 2
1 Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Shaanxi 710072, P. R. China
2 School of Information, Xi'an University of Finance and Economics, Xi'an, Shaanxi 710061, P. R. China

Abstract     Full Text  PPT

A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate 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}$ with $s=3,4$. We can construct infinite many new classes of such integral graphs by solving some certain Diophantine equations. These results are different from those in the existing literature. For $s=4$, we give a positive answer to a question of Wang et al. (Wang, Li, Hoede, Integral complete $r$-partite graphs, {\it Discrete Math.} {\bf 283} (2004) 231--241). The problem of the existence of integral complete multipartite graphs $K_{ a_1 \cdot p_1, a_2 \cdot p_2, \ldots, a_s \cdot p_s}$ with arbitrarily large number $s$ remains open.