“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 112
School of Mathematics
  Title:   On clique polynomials
1.  M.L. Mehrabadi
2.  H. Hajiabolhassan
  Status:   Published
  Journal: Australas. J. Combin.
  Vol.:  18
  Year:  1998
  Pages:   313-316
  Supported by:  IPM
Let G be a simple graph. We assign a polynomial C(G;x) to G, called the clique polynomial, where the coefficient of xi,i > 0, is the number of cliques of G with i vertices and the constant term is 1. Fisher and Solow (1990), proved that this polynomial always has a real root. We prove this result by a simple and elementary method, which also implies the following results. If ζG is the greatest real root of C(G;x) then for an induced subgraph H of GH ≤ ζG, and for a spanning subgraph H of G, ζH ≥ ζG. As a consequence of the first inequality we have α(G) ≤ −1/ζG, where α(G) denotes the independence number of G.

Download TeX format
back to top
scroll left or right