TY - JOUR
T1 - Integral complete multipartite graphs
AU - Wang, Ligong
AU - Liu, Xiaodong
PY - 2008/9/6
Y1 - 2008/9/6
N2 - A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate integral complete r-partite graphs Kp1, p2, ..., pr = Ka1 · p1, a2 · p2, ..., as · ps 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. [Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs Ka1 · p1, a2 · p2, ..., as · ps with arbitrarily large number s remains open.
AB - A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate integral complete r-partite graphs Kp1, p2, ..., pr = Ka1 · p1, a2 · p2, ..., as · ps 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. [Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs Ka1 · p1, a2 · p2, ..., as · 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=44149107809&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2007.07.084
DO - 10.1016/j.disc.2007.07.084
M3 - 文章
AN - SCOPUS:44149107809
SN - 0012-365X
VL - 308
SP - 3860
EP - 3870
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 17
ER -