• 1
  • 2
  • 3
  • 4
IPM
30
YEARS OLD

“School of Mathematics”

Paper   IPM / M / 112
   School of Mathematics
  Title: On clique polynomials
  Author(s):
1 . M.L. Mehrabadi
2 . H. Hajiabolhassan
  Status: Published
  Journal: Australas. J. Combin.
  Vol.: 18
  Year: 1998
  Pages: 313-316
  Supported by: IPM
  Abstract:
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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right