2022/01/10 by Steinerberger, Stefan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.03489
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 maximal degree Δ | ∂ 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.