Binding Number

The binding number of a simple graph with at least one graph vertex is

(1)

where is the union of the open graph neighborhoods. In particular, can intersect . Woodall (1973) introduced this measure of vertex expansion.

The binding number is 0 iff the graph has an isolated vertex. For , a complete graph satisfies . For positive , a complete bipartite graph satisfies

(2)

For a noncomplete graph , its graph toughness satisfies whenever (Goddard and Swart 1990).

Liu et al. (2026) prove that, for integers and , an -vertex simple graph with no isolated vertex and has

(3)

Equality holds precisely for , where denotes the graph join and the graph disjoint union. The exclusion of isolated vertices is essential.

The Brandt conjecture predicts for every simple graph with no complete graph as a subgraph, when is sufficiently large. Lin and Yang (2026) proved the sharp bound for every .