Integral complete multipartite graphs

Ligong Wang, Xiaodong Liu

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish
Pages (from-to)3860-3870
Number of pages11
JournalDiscrete Mathematics
Volume308
Issue number17
DOIs
StatePublished - 6 Sep 2008

Keywords

  • Complete multipartite graph
  • Diophantine equation
  • Graph spectrum
  • Integral graph

Fingerprint

Dive into the research topics of 'Integral complete multipartite graphs'. Together they form a unique fingerprint.

Cite this