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.