Boundary (graph theory)

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.

References

^ Benjamini, Itai (2013), Coarse geometry and randomness: École d'Été de Probabilités de Saint-Flour XLI – 2011, Lect. Notes Math., vol. 2100, Cham: Springer, p. 2, doi:10.1007/978-3-319-02576-6, ISBN 978-3-319-02575-9

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

[1] Benjamini, Itai (2013), Coarse geometry and randomness: École d'Été de Probabilités de Saint-Flour XLI – 2011, Lect. Notes Math., vol. 2100, Cham: Springer, p. 2, doi:10.1007/978-3-319-02576-6, ISBN 978-3-319-02575-9

[1]