The boundary of a graph and its isoperimetric inequality.

We define, for any graph G = (V , E) , a boundary ∂ G ⊆ V. The definition coincides with what one would expected for the discretization of (sufficiently nice) Euclidean domains and contains all vertices from the Chartrand, Erwin, Johns & Zhang boundary. Moreover, it satisfies an isoperimetric principle stating that graphs with many vertices have a large boundary unless they contain long paths: we show that for graphs with maximaldegree Δ | ∂ G | ≥ 1 2 Δ | V | diam (G) . For graphs discretizing Euclidean domains, one has diam (G) ∼ | V | 1 / d and recovers the scaling of the classical Euclidean isoperimetric principle. [ABSTRACT FROM AUTHOR]