Discrete isoperimetric inequalities on the strong products of paths

Abstract

For a graph $G=(V,E)$ and a nonempty set $S\subseteq V$, the \emph{vertex boundary} of $S$, denoted by ${\partial }_G(S)$, is defined to be the set of vertices that are not in $S$ but have at least one neighbor in $S$. In this paper, for $G$ being a strong product of two paths, we determine the cases in which $|{\partial }_G(S)|$ is minimized.

1 figure