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 Δ = 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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.1.2
References
Y. Caro, New Results on the Independence Number, Technical report, Tel Aviv University, (1979).
C.S. Edwards and C.H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discret. Appl. Math., 5 (1983), 51–64.
S. Filipovski, Improved Cauchy-Schwarz inequality and its applications, Turkish J. Ineq. 3(2) (2019), 8–12.
X. Li and H. Zhao, Trees with the first three smallest and largest generalized topological indices, MATCH Commun. Math. Comput. Chem. 50 (2004), 57–62.
X. Li and J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem. 54 (2005), 195–208.
W. Mantel, Solution to Problem 28, by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh, and W.A. Wythoff, Wiskundige Opgaven 10 (1907), 60–61.
B.R. Myers and R. Liu, Alower bound on the chromatic number of a graph, Networks 1 (1972), 273–277.
P. Tur' an, On an extremal problem in graph theory, Mat. Lapok 48 (1941), 436–452 (in Hungarian).
V.K. Wei, A Lower Bound on the Stability Number of a Simple Graph, Technical Report 81–11217–9, Bell Laboratories, (1981).
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.<div class="statcounter"><a title="web analytics" href="http://statcounter.com/" target="_blank"><img class="statcounter" src="//c.statcounter.com/11284516/0/7b1b10eb/1/" alt="web analytics"></a></div>