Generator-Preserving Contractions and a Min-Max Result on the Graphs of Planar Polyminoes

Abstract

In this paper, we deal with the convex generators of a graph $G=(V(G),E(G))$. A convex generator being a minimal set whose convex hull is $V(G)$, we show that it is included in the “boundary” of $G$. Then we show that the “boundary” of a polymino’s graph, or more precisely the seaweed’s “boundary”, enjoys some nice properties which permit us to prove that for such a graph $G$, the minimal size of a convex generator is equal to the maximal number of hanging vertices of a tree $T$, obtained from $G$ by a sequence of generator-preserving contractions.