Integral complete r-partite graphs

Ligong Wang, Xueliang Li, C. Hoede

Research output: Contribution to journalArticleAcademic

20 Citations (Scopus)
41 Downloads (Pure)

Abstract

A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving some Diophantine equations. The discovery of these integral complete r-partite graphs is a new contribution to the search of such integral graphs. Finally, we propose several basic open problems for further study.
Original languageEnglish
Pages (from-to)231-241
JournalDiscrete mathematics
Volume283
Issue number1-3
DOIs
Publication statusPublished - 2004

Fingerprint

Integral Graphs
Graph in graph theory
Diophantine equation
Adjacency Matrix
Open Problems
Eigenvalue
Necessary Conditions
Integer
Sufficient Conditions

Keywords

  • Diophantine equation
  • Integral graph
  • Graph spectrum
  • IR-76197
  • Complete r-partite graph

Cite this

Wang, Ligong ; Li, Xueliang ; Hoede, C. / Integral complete r-partite graphs. In: Discrete mathematics. 2004 ; Vol. 283, No. 1-3. pp. 231-241.
@article{006b5df1613a4a7db5945247146560b7,
title = "Integral complete r-partite graphs",
abstract = "A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving some Diophantine equations. The discovery of these integral complete r-partite graphs is a new contribution to the search of such integral graphs. Finally, we propose several basic open problems for further study.",
keywords = "Diophantine equation, Integral graph, Graph spectrum, IR-76197, Complete r-partite graph",
author = "Ligong Wang and Xueliang Li and C. Hoede",
year = "2004",
doi = "10.1016/j.disc.2004.02.011",
language = "English",
volume = "283",
pages = "231--241",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "1-3",

}

Wang, L, Li, X & Hoede, C 2004, 'Integral complete r-partite graphs' Discrete mathematics, vol. 283, no. 1-3, pp. 231-241. https://doi.org/10.1016/j.disc.2004.02.011

Integral complete r-partite graphs. / Wang, Ligong; Li, Xueliang; Hoede, C.

In: Discrete mathematics, Vol. 283, No. 1-3, 2004, p. 231-241.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Integral complete r-partite graphs

AU - Wang, Ligong

AU - Li, Xueliang

AU - Hoede, C.

PY - 2004

Y1 - 2004

N2 - A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving some Diophantine equations. The discovery of these integral complete r-partite graphs is a new contribution to the search of such integral graphs. Finally, we propose several basic open problems for further study.

AB - A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving some Diophantine equations. The discovery of these integral complete r-partite graphs is a new contribution to the search of such integral graphs. Finally, we propose several basic open problems for further study.

KW - Diophantine equation

KW - Integral graph

KW - Graph spectrum

KW - IR-76197

KW - Complete r-partite graph

U2 - 10.1016/j.disc.2004.02.011

DO - 10.1016/j.disc.2004.02.011

M3 - Article

VL - 283

SP - 231

EP - 241

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 1-3

ER -