TY - BOOK

T1 - A survey of results on integral trees and integral graphs

AU - Wang, Ligong

N1 - Imported from MEMORANDA

PY - 2005

Y1 - 2005

N2 - 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:

AB - 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:

KW - MSC-05C05

KW - MSC-11D09

KW - METIS-225503

KW - IR-65947

KW - EWI-3583

KW - MSC-11D41

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - A survey of results on integral trees and integral graphs

PB - University of Twente

CY - Enschede

ER -