论文标题
具有最小顶点边界的平面晶格子集
Planar lattice subsets with minimal vertex boundary
论文作者
论文摘要
如果在相同大小的所有子集中，其顶点边界最小，则图的顶点的子集很小。我们给出了平面整数晶格X的最小设置的完整，几何表征。我们的表征阐明了所有最小设置的结构，并且我们能够使用它来获得多个应用程序。我们表征了X的独特最小值集：那些与其他相同大小的其他最小值相一致的X。我们还对所有具有固定顶点边界的所有此类集合中具有最大大小的X：最大大小的X：最大尺寸进行了分类。我们定义和调查了最小集的图形g，其顶点是x的最小值集的一致性类别，其边缘连接顶点，这些顶点可以用最小的集合来表示，而最小集合完全不同，这些集合完全不同。我们证明G具有一个无限的成分，具有无限的孤立顶点，并且具有任意尺寸的组件。最后，我们证明了所有最小设置（除一个除外）已连接。
A subset of vertices of a graph is minimal if, within all subsets of the same size, its vertex boundary is minimal. We give a complete, geometric characterization of minimal sets for the planar integer lattice X. Our characterization elucidates the structure of all minimal sets, and we are able to use it to obtain several applications. We characterize uniquely minimal sets of X: those which are congruent to any other minimal set of the same size. We also classify all efficient sets of X: those that have maximal size amongst all such sets with a fixed vertex boundary. We define and investigate the graph G of minimal sets whose vertices are congruence classes of minimal sets of X and whose edges connect vertices which can be represented by minimal sets that differ by exactly one vertex. We prove that G has exactly one infinite component, has infinitely many isolated vertices and has bounded components of arbitrarily large size. Finally, we show that all minimal sets, except one, are connected.
