MSc Defence: Vertex Isoperimetry of Complete q-ary Trees

Candidate: Lazar Mandic

Supervisor: Dr. Anthony Bonato

Abstract
We improve on previously known upper and lower boundaries for the vertex isoperimetric parameter on complete q-ary trees. The vertex isoperimetric parameter is the maximum possible minimum neighbor set of a set of vertices in a graph. For a complete q-ary tree with a depth d, if q ≥ 5, then we find that the vertex isoperimetric parameter is exactly d. If q = 3 or q = 4, then we find that there are only three possible exact values, and if q = 2, the bounds from d/2 by only a logarithmic term. We define local isomorphisms and internal vertices to simplify the problem down to four vertices, and later on, we define left-compressions, down-compressions, and aeolian compressions to use in our algorithm to find a limited structure for certain vertex sets.