Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
Chapter 4: The Vertex-Isoperimetric Problem
Having developed the Steiner operations, stabilization and compression, for the edge-isoperimetric problem, we now explore the possibility of applying them to another isoperimetric problem on graphs, the vertex-isoperimetric problem (VIP). This chapter revisits the material of the first three chapters with the VIP in place of the EIP. The development of global methods for the VIP can be condensed because it is largely the same, but there are differences and the differences are instructive.
4.1 Definitions and Examples
4.1.1 The VIP
For a graph G = ( V, E, ?) and S ? V, the vertex-boundary of S is
In words, the vertex boundary of S is the set of vertices not in S but having neighbors in S. Then given k ? 
+, the vertex-isoperimetric problem is to minimize ? ( S) over all S ? V such that S = k. The VIP is trivial on K n so we look at n. First, we exhibit, in Fig. 4.1, some 2-sets in 8 which have vertex-boundaries of differing sizes.
Fig. 4.1: ? (S) = 4, 3, 2 respectively.
4.1.1.1 Exercise
Show that ? n and 0 < k < n,
4.2 Stabilization and VIP
Theorem 4.1
? S ? V, ? ( 
) ? ? ( S).
Proof Suppose that 
but w ? ? ( S). Clearly w
Copyright Cambridge University Press 2004 under license agreement with Books24x7
