Vertex isoperimetric inequalities for a family of graphs on Z^k

zbMATH Open1252.05094arXiv1202.4204MaRDI QIDQ456299FDOQ456299

Authors: Ellen Veomett, Andrew John Radcliffe 

Publication date: 24 October 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the family of graphs whose vertex set is Z^k where two vertices are connected by an edge when their linfty-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.

Full work available at URL: https://arxiv.org/abs/1202.4204

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An approximate vertex-isoperimetric inequality for \(r\)-sets
• Compressions and isoperimetric inequalities
• Isoperimetry in integer lattices
• The vertex isoperimetric problem for the powers of the diamond graph
• Publication:4888931

zbMATH Keywords

discrete isoperimetric inequalities

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Cited In (14)

• Planar lattice subsets with minimal vertex boundary
• Vertex isoperimetric parameter of a computation graph
• On a characterization of lattice cubes via discrete isoperimetric inequalities
• An approximate vertex-isoperimetric inequality for \(r\)-sets
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Interpolating between volume and lattice point enumerator with successive minima
• Isoperimetry in integer lattices
• Isoperimetric stability in lattices
• The vertex-isoperimetric number of the incidence and non-incidence graphs of unitals
• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• The vertex isoperimetric problem for the powers of the diamond graph
• On discrete Brunn-Minkowski and isoperimetric type inequalities
• An extremal graph problem on a grid and an isoperimetric problem for polyominoes

This page was built for publication: Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456299)