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 等数据库收录! |
|