Integral trees of diameter 6

Ligong Wang, Haitze J. Broersma, C. Hoede, Xueliang Li, X. Li, Georg J. Still

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
26 Downloads (Pure)

Abstract

A graph $G$ is called integral if all eigenvalues of its adjacency matrix $A(G)$ are integers. In this paper, the trees $T(p,q)\cdot T(r,m,t)$ and $K_{1,s}\cdot T(p,q)\cdot T(r,m,t)$ of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349–362].
Original languageEnglish
Pages (from-to)1254-1266
Number of pages13
JournalDiscrete applied mathematics
Volume155
Issue number4542/10
DOIs
Publication statusPublished - 15 May 2007

Keywords

  • Integral tree
  • Characteristic polynomial
  • Graph spectrum

Fingerprint Dive into the research topics of 'Integral trees of diameter 6'. Together they form a unique fingerprint.

Cite this