On Clique Mantel's Theorem

Document Type : Research Paper

Author

Department of Mathematics and Computer Science, Allameh Tabataba’i University, Tehran, Iran

Abstract

A complete subgraph of any simple graph G on k vertices is called a k-clique of G. In this paper, we first introduce the concept of the value of a k-clique (k>1) as an extension of the idea of the degree of a given vertex. Then, we obtain
the generalized version of handshaking lemma which we call it clique handshaking lemma. The well-known classical result of Mantel states that the maximum number of edges in the class of triangle-free graphs with n vertices is equal to n2/4. Our main goal here is to find an extension of the above result for the class of Kω+1-free graphs, using the ideas of the value of cliques and the clique handshaking lemma.

Keywords

References

  1. W. Mantel, Solution to Problem 28, by H, Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh, and WA Wythoff, Wiskundige Opgaven, 10, 60–61 (1907).
  2. W. T. Tutte, All the king’s horses. A guide to reconstruction., In Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977). Academic Press, New York, (1979).
  3. D. Conlon, J. Fox andB. Sudakov, Books versus Triangles at the Extremal Density, SIAM Journal on Discrete Mathematics, 34, 385–398 (2020).
  4. B. Brešar, W. Imrich and S. Klavžar, Reconstructing subgraph-counting graph polynomials of increasing families of graphs, Discrete Mathematics, 297, 159–166 (2005).
  5. D. B. West, Intorduction to Graph Theory (Second edition), Prentice-Hall , (2001).
  6. O. Knill, On Index Expectation and Curvature for Networks, arXiv:1202.4514, (2012)
Analytical and Numerical Solutions for Nonlinear Equations
Volume 7, Issue 2
September 2022
Pages 171-178

Files

History

  • Receive Date: 30 November 2022
  • Accept Date: 20 April 2023

Share

How to cite

Statistics