DENSE GRAPHS WITHOUT 3-REGULAR SUBGRAPHS

摘要

In this paper, we show the existence of graphs with cn log log n edges that contain no 3-regular subgraphs. On the other hand, we show that graphs with c(k)n log Delta(G) edges contain k-regular subgraphs. We also consider a related problem for graphs with cn(2) edges. (C) 1995 Academic Press, Inc. [References: 17]