论文标题
图的边界及其等级不等式
The Boundary of a Graph and its Isoperimetric Inequality
论文作者
论文摘要
我们定义任何图形$ g =（v，e）$，一个边界$ \ partial g \ subseteq v $。该定义与人们期望的（足够好的）欧几里得域的离散化相吻合，并包含来自chartrand-erwin-johns-zhang边界的所有顶点。此外，它满足了一个等级原理，表明具有许多顶点的图具有较大的边界，除非它们包含较长的路径：我们证明对于具有最大程度的图形$δ$ $$ | \部分g | \geq \frac{1}{2Δ} \frac{|V|}{\mbox{diam}(G)}.$$ For graphs discretizing Euclidean domains, one has $\mbox{diam}(G) \sim |V|^{1/d}$ and recovers the scaling of the classical Euclidean isoperimetric 原则。
We define, for any graph $G=(V,E)$, a boundary $\partial G \subseteq 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 $Δ$ $$ | \partial G| \geq \frac{1}{2Δ} \frac{|V|}{\mbox{diam}(G)}.$$ For graphs discretizing Euclidean domains, one has $\mbox{diam}(G) \sim |V|^{1/d}$ and recovers the scaling of the classical Euclidean isoperimetric principle.
