首页 | 本学科首页   官方微博 | 高级检索  
     

On the Covering of the Vertices of a Graph by Cliques
作者姓名:Paul Erdos
作者单位:Magyar Tudomanyos
摘    要:In conversation I was told by Professor R.Brigham the following conjecture [1].Let G(n) be a graph of n vertices.Denote by f(G(n))=t the smallest integer for which the vertices of G(n) can be covered by t cliques. Denote further by h(G(n)) =l the largest integer for which there are l edges of our G(n) no two of Which are in the same clique.Clearly h(G(n)) can be much larger than f(G(n))e.g.if n=2m and G(n) is the complete bipartite graph of m white and m black vertices.Then l(G(n))=m and l(G(n))=m~2. It was conjectured that if G(n).has no isolated vertices then

本文献已被 CNKI 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号