On clique values identities and mantel-type theorems

Document Type : Research Paper

Author

Department of Mathematics and Computer Science, Allameh Tabatabai University, Tehran, Iran.

Abstract

‎In this paper‎, ‎we first extend the weighted handshaking‎ ‎lemma‎, ‎using a generalization of the concept of the degree of vertices to the values of graphs‎. ‎This edge-version of the weighted handshaking lemma yields an immediate generalization of the‎ ‎Mantel's classical result which asks for the maximum number of edges in triangle-free graphs‎ ‎to the class of $K_{4}$-free graphs‎. ‎Then‎, ‎by defining the concept of value‎ ‎for cliques (complete subgraphs) of higher orders‎, ‎we also‎ ‎extend the classical result of Mantel for any graph $G$‎. ‎We finally conclude our paper with a discussion‎ ‎about the possible future works‎.

Keywords

Main Subjects


[1] J. A. Bondy and S. R. Murty, Graph theory with applications, New York, 1976.
[2] P. J. Kelly, On Isometric Transformations, PhD thesis, University of Wisconsin - Madison, 1942.
[3] W. Mantel, Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff),
Wiskundige Opgaven., 18 (1907) 60–61.
[4] P. Turán, On an extremal problem in graph theory, (Hungarian), Mat. Fiz. Lapok, 48 (1941) 436–452.
[5] J. M. Steele, The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities, The Math-
ematical Association of America, Washington, DC; Cambridge University Press, Cambridge, 2004.
[6] B. Wu, The weighted version of the handshaking lemma with an application, J. Ineq. Appl., 351 (2014) 1–5.
[7] M. Aigner, Turán’s graph theorem, Amer. Math. Month., 102 (1995) 808–816.
[8] D. C. Fisher, The number of triangles in K4 -free graph, Disc. Math., 69 (1988) 203–205.
[9] J. Eckhoff, The maximum number of triangles in a K4-free graph, Disc. Math., 194 (1999) 95–106.
[10] D. C. Fisher and J. Ryan, Bound on the number of complete subgraphs, Disc. Math., 103 (1992) 313–320.
[11] V. Nikiforov, The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc., 363 (2011) 1599–
1618.
[12] A. A. Razborov, On the minimal density of triangles in graphs, Combin. Prob. Comput., 17 (2008) 603–618.
Volume 9, Issue 3 - Serial Number 3
September 2020
Pages 139-146
  • Receive Date: 08 October 2019
  • Revise Date: 20 May 2020
  • Accept Date: 27 May 2020
  • Published Online: 01 September 2020