Integral complete multipartite graphs

Ligong Wang; Xiaodong Liu

doi:10.1016/j.disc.2007.07.084

Integral complete multipartite graphs

Ligong Wang, Xiaodong Liu

School of Mathematics and Statistics

Xi'an University of Finance and Economics

Research output: Contribution to journal › Article › peer-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 K_{p1, p2, ..., pr} = K_{a1 · 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 K_{a1 · 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	https://doi.org/10.1016/j.disc.2007.07.084
State	Published - 6 Sep 2008

Keywords

Complete multipartite graph
Diophantine equation
Graph spectrum
Integral graph

Access to Document

10.1016/j.disc.2007.07.084

Cite this

@article{8fc702529a19496a905b8207796da013,

title = "Integral complete multipartite graphs",

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.",

keywords = "Complete multipartite graph, Diophantine equation, Graph spectrum, Integral graph",

author = "Ligong Wang and Xiaodong Liu",

year = "2008",

month = sep,

day = "6",

doi = "10.1016/j.disc.2007.07.084",

language = "英语",

volume = "308",

pages = "3860--3870",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "17",

}

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 -

Integral complete multipartite graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this