Binding Number

The binding number of a nonempty simple graph 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)

The 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.