K-PSEUDOSNAKES IN LARGE GRIDS
Author
Matamala Vasquez, Martin IgnacioPrisner, Erich
Rapaport Zimermann, Ivan
Abstract
We study the problem of finding maximum induced subgraphs of bounded maximum degree k-so-called “k-pseudosnakes”- in D-dimensional grids with all side lengths large. We prove several asymptotic upper bounds and give several lower bounds based on constructions. The constructions turn out to be asymptotically optimal for every D when k = 0, 1,D, 2D - 2, 2D - 1 and 2D.
Book's title
LATIN 2002
Start page
224
End page
235