Boundary (graph theory)

Short description: Graph nodes linked to, but not part of, a subgraph

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., 2100, Cham: Springer, p. 2, doi:10.1007/978-3-319-02576-6, ISBN 978-3-319-02575-9

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Boundary (graph theory). Read more

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

[1]