Using a technique of Erdos, we show that for any given M ＞ 0 and e ＞ 0,there exist δ = δ(M, ε) ＞ 0 and a graph G of any large order n such that the density ofG is at least M, while the density of the subgraph induced by any subset U V(G) with|U| ≤δn is less than 1 + ε. The constant 1 + e cannot be improved to 1.
Local densityglobal densityrandom graph
Li Yusheng
展开 >
Department of Mathematics, Hohai University, Nanjing 210098, China
NETL
NSTL
万方数据
维普
