On the clique number and Mantel/Turan theorems

Let G=(V,E) be a finite undirected graph with vertex set V(G) of order |V(G)|=n and edge set E(G) of size |E(G)|=m. Let d_{1}\geq d_{2}\geq…\geq d_{n} be the degree sequence of the graph G.

A clique in a graph G is a complete subgraph of G.  A clique is called maximum if it has maximum cardinality.
The clique number of a graph G, denoted \omega(G), is the order of a maximum clique of G.

In 1907 Mantel proved that a triangle-free graph with n vertices can contain at most  $lfloor \frac{n^{2}}{4}\rfloor edges. In 1941 Tur\’ an generalized Mantel’s result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced K_{r} have at most (1-\frac{1}{r-1}) \frac{n^{2}}{2} edges.

In this talk, we present new lower bounds for the clique number \omega(G). Moreover, we obtain a new bound for the maximum number of edges in a K_{r}-free graph G of order n, with minimum degree d_{n}, and
maximum degree d_{1}. 

The results are based on elementary inequalities applied to the degree sequence d_{1}\geq d_{2}\geq\ldots \geq d_{n}.

We are looking forward to meeting at the video conference.

Join Zoom Meeting HERE!