A survey of results on integral trees and integral graphs

Ligong Wang

Research output: Book/ReportReportProfessional

147 Downloads (Pure)


A graph $G$ is called {\it integral} if all zeros of the characteristic polynomial $P(G,x)$ are integers. Our purpose is to determine or to characterize which graphs are integral. This problem was posed by Harary and Schwenk in 1974. In general, the problem of characterizing integral graphs seems to be very difficult. Thus, it makes sense to restrict our investigations to some interesting families of graphs. So far, there are many results on some particular classes of integral graphs. For example, some results for integral graphs with maximum degree 3 and 4 have been obtained by Cvetkovi\'c (1974, 1975, 1998), Schwenk (1978), Simi\'c (1986, 1995, 1998, 2001, 2002), Bali{\'{n}}ska (1999, 2001, 2002, 2004) and others. An infinite family of integral complete tripartite graphs was constructed by Roitman (1984). Results on integral graphs which belong to the class $\overline{\alpha K\sb {a,b}}$, $\overline{\alpha K\sb a\cup\beta K\sb b}$ or $\overline{\alpha K_a \cup \beta K_{b,b}}$ were presented by Lepovi{\'{c}} (2003, 2004). Trees present another important family of graphs for which the problem has been considered by Harary (1974), Schwenk (1974, 1979), Watanabe (1979), Li(1987, 1999, 2000, 2002, 2004), Liu(1988), Cao (1988, 1991), Yuan(1998), H{\'{i}}c(1997, 1998, 2003), Wang (1999, 2000, 2002, 2004) and others. Moreover, several graph operations (e.g., Cartesian product, strong sum and product) on integral graphs can be used for constructing infinite families of integral graphs with increasing order. In this paper, I shall give a survey of results on integral trees and integral graphs. Our main contributions on integral graphs during the last years concern the following topics:
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages23
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-05C05
  • MSC-11D09
  • METIS-225503
  • IR-65947
  • EWI-3583
  • MSC-11D41

Cite this