Isoperimetric number of a graph

ID: isoperimetric-number-of-a-graph

For a finite graph with at least two vertices, the displayed minimum measures the fewest outgoing edges per vertex in a nonempty set occupying at most half the graph. It uses the edge boundary, rather than the external vertex boundary. For the hypercube graph , , it equals one: edge-isoperimetry gives the lower bound and a coordinate half-cube attains it.

New to topics? Read the docs here!