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


Large dense neighbourhoods and turán's theorem
Authors:JA Bondy
Institution:University of Waterloo, Ontario, Canada
Abstract:Let tr(n) denote the number of edges in the complete r-partite graph on n vertices whose colour classes are as equal in size as possible. It is proved that if G is a simple graph on n vertices and more than tr(n) edges, and if v is any vertex of maximum degree m in G, then the subgraph of G induced by the neighbours of v has more than tr?1(m) edges. Examples are given to demonstrate the sharpness of this theorem, and its algorithmic implications are noted.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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