TY - JOUR
T1 - Integral complete multipartite graphs Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with s = 5, 6
AU - Wang, Ligong
AU - Wang, Qi
PY - 2010/2/28
Y1 - 2010/2/28
N2 - A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In our recent work, we have studied integral complete r-partite graphs Kp1, p2, ..., pr = Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with s = 3, 4 (also see, L.G. Wang, X.D. Liu, Integral complete multipartite graphs, Discrete Math. 308 (2008) 3860-3870 ). In this paper, we continue the work on such integral graphs, we investigate integral complete multipartite graphs Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with s = 5, 6 for the first time by computer search. Then we 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 = 5, 6, we give a positive answer to a question of Wang et al. [L.G. Wang, X.L. Li, C. Hoede, Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with arbitrarily large number s remains open.
AB - A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In our recent work, we have studied integral complete r-partite graphs Kp1, p2, ..., pr = Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with s = 3, 4 (also see, L.G. Wang, X.D. Liu, Integral complete multipartite graphs, Discrete Math. 308 (2008) 3860-3870 ). In this paper, we continue the work on such integral graphs, we investigate integral complete multipartite graphs Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with s = 5, 6 for the first time by computer search. Then we 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 = 5, 6, we give a positive answer to a question of Wang et al. [L.G. Wang, X.L. Li, C. Hoede, Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs Ka1 {dot operator} p1, a2 {dot operator} p2, ..., as {dot operator} ps with arbitrarily large number s remains open.
KW - Complete multipartite graph
KW - Diophantine equation
KW - Graph spectrum
KW - Integral graph
UR - http://www.scopus.com/inward/record.url?scp=71649088079&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2009.09.016
DO - 10.1016/j.disc.2009.09.016
M3 - 文章
AN - SCOPUS:71649088079
SN - 0012-365X
VL - 310
SP - 812
EP - 818
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 4
ER -