19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Clique Polynomial and A New Proof of Turan's Theorem for $K_{t+1}$-Free Graphs

Presented by Dr. Hossein TEIMOORI FAAL
Type: Oral presentation
Track: General session


For a given simple graph $G$, we define an $i$-clique as a complete subgraph of $G$ on $i$ vertices. The generating function for the number of $i$-cliques in $G$ is called the "clique polynomial" of $G$. Using elementary tools form Calculus, Hajiabolhasan and Mehrabadi showed that this polynomial has always a real root for any given simple graph $G$. As an immediate consequence, they gave a new proof of the Mantel's theorem for triangle-free graphs. In this paper, using similar tools form Calculus, we present a new proof of Turan's theorem for $K_{t+1}$-free graphs which is a generalization of Mantel's theorem.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

  • Dr. Hossein TEIMOORI FAAL Department of Applied Mathematics of Charles University in Prague and Institute for Theoretical Computer Science(ITI)


  • Dr. Morteza BAYAT Department of Electriacl and Computer Engineering, Zanjan University