Some families of integral graphs

Ligong Wang; Hajo Broersma; Cornelis Hoede; Xueliang Li; Georg Still

doi:10.1016/j.disc.2007.12.010

Some families of integral graphs

Ligong Wang
, Hajo Broersma
, Cornelis Hoede
, Xueliang Li
, Georg Still

School of Mathematics and Statistics

Faculty of Electrical Engineering, Mathematics and Computer Science
Nankai University

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs K_{1, r} • K_n, r * K_n, K_{1, r} • K_{m, n}, r * K_{m, n} and the tree K_{1, s} • T (q, r, m, t) are defined. We determine the characteristic polynomials of these graphs and also obtain sufficient and necessary conditions for these graphs to be integral. Some sufficient conditions are found by using the number theory and computer search. All these classes are infinite. Some new results which treat interrelations between integral trees of various diameters are also found. The discovery of these integral graphs is a new contribution to the search of such graphs.

Original language	English
Pages (from-to)	6383-6391
Number of pages	9
Journal	Discrete Mathematics
Volume	308
Issue number	24
DOIs	https://doi.org/10.1016/j.disc.2007.12.010
State	Published - 28 Dec 2008

Keywords

General Pell's equation
Integral graph
Integral tree
Spectrum

Access to Document

10.1016/j.disc.2007.12.010

Cite this

@article{712c0575a0b546cba8494816c77cb81c,

title = "Some families of integral graphs",

abstract = "A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs K1, r • Kn, r * Kn, K1, r • Km, n, r * Km, n and the tree K1, s • T (q, r, m, t) are defined. We determine the characteristic polynomials of these graphs and also obtain sufficient and necessary conditions for these graphs to be integral. Some sufficient conditions are found by using the number theory and computer search. All these classes are infinite. Some new results which treat interrelations between integral trees of various diameters are also found. The discovery of these integral graphs is a new contribution to the search of such graphs.",

keywords = "General Pell's equation, Integral graph, Integral tree, Spectrum",

author = "Ligong Wang and Hajo Broersma and Cornelis Hoede and Xueliang Li and Georg Still",

year = "2008",

month = dec,

day = "28",

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

language = "英语",

volume = "308",

pages = "6383--6391",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "24",

}

TY - JOUR

T1 - Some families of integral graphs

AU - Wang, Ligong

AU - Broersma, Hajo

AU - Hoede, Cornelis

AU - Li, Xueliang

AU - Still, Georg

PY - 2008/12/28

Y1 - 2008/12/28

N2 - A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs K1, r • Kn, r * Kn, K1, r • Km, n, r * Km, n and the tree K1, s • T (q, r, m, t) are defined. We determine the characteristic polynomials of these graphs and also obtain sufficient and necessary conditions for these graphs to be integral. Some sufficient conditions are found by using the number theory and computer search. All these classes are infinite. Some new results which treat interrelations between integral trees of various diameters are also found. The discovery of these integral graphs is a new contribution to the search of such graphs.

AB - A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs K1, r • Kn, r * Kn, K1, r • Km, n, r * Km, n and the tree K1, s • T (q, r, m, t) are defined. We determine the characteristic polynomials of these graphs and also obtain sufficient and necessary conditions for these graphs to be integral. Some sufficient conditions are found by using the number theory and computer search. All these classes are infinite. Some new results which treat interrelations between integral trees of various diameters are also found. The discovery of these integral graphs is a new contribution to the search of such graphs.

KW - General Pell's equation

KW - Integral graph

KW - Integral tree

KW - Spectrum

UR - https://www.scopus.com/pages/publications/56649107923

U2 - 10.1016/j.disc.2007.12.010

DO - 10.1016/j.disc.2007.12.010

M3 - 文章

AN - SCOPUS:56649107923

SN - 0012-365X

VL - 308

SP - 6383

EP - 6391

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 24

ER -

Some families of integral graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this