“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 112  


Abstract:  
Let G be a simple graph. We assign a polynomial C(G;x) to G, called the clique polynomial, where the coefficient of x^{i},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 G,ζ_{H} ≤ ζ_{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 