# A survey of results on integral trees and integral graphs

Ligong Wang

Research output: Book/ReportReportProfessional

88 Downloads (Pure)

## Abstract

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 language Undefined Enschede University of Twente 23 0169-2690 Published - 2005

### Publication series

Name Memorandum Afdeling TW Department of Applied Mathematics, University of Twente 1763 0169-2690

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