This article relies largely or entirely on a
single source. (April 2024) |
In graph theory, the outer boundary of a subset S of the vertices of a graph G is the set of vertices in G that are adjacent to vertices in S, but not in S themselves. The inner boundary is the set of vertices in S that have a neighbor outside S. The edge boundary is the set of edges with one endpoint in the inner boundary and one endpoint in the outer boundary. [1]
These boundaries and their sizes are particularly relevant for isoperimetric problems in graphs, separator theorems, minimum cuts, expander graphs, and percolation theory.
This article relies largely or entirely on a
single source. (April 2024) |
In graph theory, the outer boundary of a subset S of the vertices of a graph G is the set of vertices in G that are adjacent to vertices in S, but not in S themselves. The inner boundary is the set of vertices in S that have a neighbor outside S. The edge boundary is the set of edges with one endpoint in the inner boundary and one endpoint in the outer boundary. [1]
These boundaries and their sizes are particularly relevant for isoperimetric problems in graphs, separator theorems, minimum cuts, expander graphs, and percolation theory.