Boundary (graph theory)
{{short description|Graph nodes linked to, but not part of, a subgraph}}
{{one source |date=April 2024}}
In graph theory, the outer boundary of a subset {{mvar|S}} of the vertices of a graph {{mvar|G}} is the set of vertices in {{mvar|G}} that are adjacent to vertices in {{mvar|S}}, but not in {{mvar|S}} themselves. The inner boundary is the set of vertices in {{mvar|S}} that have a neighbor outside {{mvar|S}}. The edge boundary is the set of edges with one endpoint in the inner boundary and one endpoint in the outer boundary.{{citation
| last = Benjamini | first = Itai
| doi = 10.1007/978-3-319-02576-6
| isbn = 978-3-319-02575-9
| page = 2
| publisher = Springer | location = Cham
| series = Lect. Notes Math.
| title = Coarse geometry and randomness: École d'Été de Probabilités de Saint-Flour XLI – 2011
| volume = 2100
| year = 2013}}
These boundaries and their sizes are particularly relevant for isoperimetric problems in graphs, separator theorems, minimum cuts, expander graphs, and percolation theory.