Geodesic
Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
Ellen Veomett1 ; Andrew John Radcliffe2
1Saint Mary's College of California
2University of Nebraska, Lincoln
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider the family of graphs whose vertex set is $\mathbb{Z}^k$ where two vertices are connected by an edge when their $\ell_\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 \mathbb{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.
DOI : 10.37236/2426
Classification : 05C35, 05C75, 60E15
Mots-clés : discrete isoperimetric inequalities

Ellen Veomett  1   ; Andrew John Radcliffe  2

1 Saint Mary's College of California
2 University of Nebraska, Lincoln 
@article{10_37236_2426,
     author = {Ellen Veomett and Andrew John Radcliffe},
     title = {Vertex isoperimetric inequalities for a family of graphs on {\(\mathbb{Z}^k\)}},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {2},
     doi = {10.37236/2426},
     zbl = {1252.05094},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2426/}
}
TY  - JOUR
AU  - Ellen Veomett
AU  - Andrew John Radcliffe
TI  - Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2426/
DO  - 10.37236/2426
ID  - 10_37236_2426
ER  - 
%0 Journal Article
%A Ellen Veomett
%A Andrew John Radcliffe
%T Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2426/
%R 10.37236/2426
%F 10_37236_2426
Ellen Veomett; Andrew John Radcliffe. Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\). The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2426

Cité par Sources :