Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 3860-3870 |
Number of pages | 11 |
Journal | Discrete Mathematics |
Volume | 308 |
Issue number | 17 |
DOIs | |
State | Published - 6 Sep 2008 |
Keywords
- Complete multipartite graph
- Diophantine equation
- Graph spectrum
- Integral graph