A refined Tur'an theorem

Abstract

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₁ ≥ d₂ ≥ ⋯ ≥ d_n = δ be the degree sequence of the graph G. A clique in a graph G is a complete subgraph of G. The clique number of a graph G, denoted by ω(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 ⌊n²/4⌋ 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 − 1/r − 1)n²/2 edges. In this paper, we give new bounds for the maximum number of edges in a K_r-free graph G of order n, minimum degree δ, and maximum degree Δ. We show that, for the families of graphs having the above properties, our bounds are slightly better than the more general bounds of Tur'an.