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}geqldots geq d_{n}.

We are looking forward to meeting at the video conference.

Join Zoom Meeting HERE!