A generalization of a Turán’s theorem about maximum clique on graphs

Douglas Frederico Guimarães Santiago, Anderson Luiz Pedrosa Porto, Kaio Ariel Silva Sá

Abstract


One of the most important Turán’s theorems establishes an inequality between the maximum clique and the number of edges of a graph. Since 1941, this result has received much attention and many of the different proofs involve induction and a probability distribution. In this paper we detail finite procedures that gives a proof for the Turán’s Theorem. Among other things, we give a generalization of this result. Also we apply this results to a Nikiforov’s inequality between the spectral radius and the maximum clique of a graph.


Keywords


maximum clique, spectral radius, Turan’s theorem, probability distribution

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.10

References

M. Aigner and G.M. Ziegler, Turán’s Graph Theorem, In: Proofs from the Book. Berlin, Heidelberg: Springer, (1998), 169-172.

N. Alon and J. Spencer, The Probabilistic Method, 2 ed. Tel Aviv and New York, Wiley Interscience, (2000).

B. Bollobás, Extremal Graph Theory, Reprint of the 1978 original. Mineola, NY: Dover Publications, (2004).

J. Bondy, and U. Murty, Graph Theory, 1 ed. Springer Publishing Company, (2008).

L. Eroh, H. Escuadro, R. Gera, and S. Prahlow, S, A graph theoretical analysis of the number of edges in k-dense graphs, Electron. J. Graph Theory Appl. 4(1) (2016), 26–41.

M. Hailat, An upper bound of edges of graphs containing no vertex-disjoint odd cycles, J. Math. Comput. Sci. 8(6) (2018), 644–653.

T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math 17 (1965), 533–540.

https://doi.org/10.4153/CJM-1965-053-6.

V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002), 179–189.

https://doi.org/10.1017/S0963548301004928.

V.S. Samoilov, An upper bound on the number of edges of a graph whose k-th power has a connected complement, Journal of Mathematical Sciences 232(1) (2018).

P. Turán, On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48 (1941), 436–452.

P. Turán, On the theory of graphs, Colloq. Math 3 (1954), 19–30. https://doi.org/10.4064/cm-3-1-19-30.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats