# Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k

Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k
We consider the family of graphs whose vertex set is Z^k where two vertices are connected by an edge when their l\infty-distance is 1. We prove the optimal vertex isoperimetric inequality for this family of graphs. That is, given a positive integer n, we find a set A \subset Z^k of size n such that the number of vertices who share an edge with some vertex in A is minimized. These sets of minimal boundary are nested, and the proof uses the technique of compression. We also show a method of calculating the vertex boundary for certain subsets in this family of graphs. This calculation and the isoperimetric inequality allow us to indirectly find the sets which minimize the function calculating the boundary.

Autor: Ellen Veomett; A. J. Radcliffe

Fuente: https://archive.org/