A refined Tur'an theorem
| Main Author: | Filipovski, Slobodan; Faculty of Mathematics, Natural Sciences and Information Technologies University of Primorska, Glagoljaška 8 6000 Koper, Slovenia |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2024
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/1868 https://www.ejgta.org/index.php/ejgta/article/view/1868/pdf_290 |
Daftar Isi:
- 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 Δ = d1 ≥ d2 ≥ ⋯ ≥ dn = δ 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 ⌊n2/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 Kr have at most (1 − 1/r − 1)n2/2 edges. In this paper, we give new bounds for the maximum number of edges in a Kr-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.