
تعداد نشریات | 43 |
تعداد شمارهها | 1,685 |
تعداد مقالات | 13,830 |
تعداد مشاهده مقاله | 32,659,791 |
تعداد دریافت فایل اصل مقاله | 12,915,423 |
On clique values identities and mantel-type theorems | ||
Transactions on Combinatorics | ||
مقاله 2، دوره 9، شماره 3، آذر 2020، صفحه 139-146 اصل مقاله (223.97 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2020.119553.1680 | ||
نویسنده | ||
Hossein Teimoori Faal* | ||
Department of Mathematics and Computer Science, Allameh Tabatabai University, Tehran, Iran. | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
Reconstruction problem؛ vertex-deck؛ handshaking lemma؛ clique value identity | ||
مراجع | ||
[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. | ||
آمار تعداد مشاهده مقاله: 252 تعداد دریافت فایل اصل مقاله: 304 |