Clique Polynomials and Chordal Graphs

Abstract: The ordinary generating function of the number of complete subgraphs of

G

is called a clique polynomial of

G

and is denoted by

C (G, x)

. A real root of

C (G, x)

is called a clique root of the graph

G

. Hajiabolhasan and Mehrabadi showed that the clique polynomial has always a real root in the interval

[- 1, 0)

. Moreover, they showed that the class of triangle-free graphs has only clique roots. Here, we generalize their result by showing that the class of

K_{4}

-free chordal graphs has also only clique roots. Moreover, we show that this class has always a clique root

- 1

. We finally conclude the paper with several important questions and conjectures.

This page was built for publication: Clique Polynomials and Chordal Graphs