Compute Boundary Vertices of a Subset in a Graph

Computes the boundary of a subset U of vertices in a graph. A vertex v is in the boundary of U if and only if v is in U and its expanded neighborhood (itself and its adjacent vertices) intersects both U and the complement of U.

Usage

set.boundary(U, adj.list)

Arguments

U: Integer vector of vertex indices representing a subset of the graph vertices. Must contain valid indices between 1 and the number of vertices in the graph.
adj.list: List where each element contains the adjacency list for a vertex. Element adj.list[[i]] contains indices of vertices adjacent to vertex i. Self-loops are ignored.

Value

Integer vector containing the indices of vertices in the boundary of U, sorted in ascending order. Returns an empty vector if U has no boundary vertices.

Details

The boundary of a subset U consists of those vertices in U that are adjacent to at least one vertex outside of U. Mathematically, v is in the boundary of U if and only if v is in U and there exists a vertex w not in U such that w is adjacent to v.

This definition is consistent with the topological notion of boundary adapted to the discrete setting of graphs.

Examples

# Create a simple graph adjacency list
adj.list <- list(c(2, 3), c(1, 3, 4), c(1, 2), c(2, 5), c(4))

# Define a subset of vertices
U <- c(1, 2, 3)

# Compute the boundary
boundary <- set.boundary(U, adj.list)
print(boundary)  # Returns c(2) since only vertex 2 is adjacent to vertex 4 (outside U)