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

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

2012-02-20

arxiv.org/abs/1202.4204v1

Mathematics

Combinatorics

19 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-563713