On the number of complete subgraphs of a graph II
On the number of complete subgraphs of a graph II
复制标题
DOI：
10.1007/978-3-0348-5438-2_41
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
L. Lovász;M. Simonovits
中科院分区：
文献类型：
--
作者：
L. Lovász;M. Simonovits
本文推广了P. Erdlers和L. Moser及J. W. Moon的一些结果，给出了完全p-图的个数Kp的下界。进一步，对于n和E的某些值，我们给出了极图的一个完全刻画，即. e.我们的结果证明了P. Erdens的猜想：当k <n/2时，具有[n ~ 2/4] +kedges的图G_n至少包含个三角形。
Generalizing some results of P.Erdősand some of L.Moserand J. W.Moonwe give lower bounds on the number of completep-graphsKpof graphs in terms of the numbers of vertices and edges. Further, for some values ofnandEwe give a complete characterization of the extremal graphs, i. e. the graphsSofnvertices andEedges having minimum number ofKp’s.Our results contain the proof of the longstanding conjecture of P.Erdősthat a graphGnwith [n2/4] +kedges contains at leasttriangles ifk<n/2.