Flip graphs of stacked and flag triangulations of the 2-sphere (Q2138560)

The edge flip operation in a planar triangulation consists of replacing an \(ac\)-edge of a quadrilateral \(abcd\) by another diagonal, the \(bd\)-edge. The flip graph of triangulated \(2\)-spheres is a graph whose nodes are isomorphism classes of \(n\)-vertex triangulated \(2\)-spheres, and two nodes are joined by an arc if and only if there is an edge flip between the two triangulations representing the nodes. From [\textit{K. Wagner}, Jahresber. Dtsch. Math.-Ver. 46, 26--32 (1936; Zbl 0014.18102)], it is known that the flip graph of \(n\)-vertex triangulated \(2\)-spheres is connected. In other words, for any two \(n\)-vertex \((n \geq 4)\) triangulated \(2\)-spheres, one can be transformed into another by a sequence of edge flips. In the article under review, the authors study the connectedness of induced subgraphs of the flip graph of triangulated \(2\)-spheres. In particular, they consider the flip graphs of \(n\)-vertex flag \(2\)-spheres and stacked \(2\)-spheres. They show that the flip graph \(\mathcal{F}_n\) of \(n\)-vertex \((n \geq 8)\) flag \(2\)-spheres has two components: one is the double cone and the other one consists of all other \(n\)-vertex flag \(2\)-spheres. However, the structure of the flip graph \(\mathcal{S}_n\) of stacked \(2\)-spheres is remarkably different. The authors show that the flip graph \(\mathcal{S}_n\) is not connected for \(n \geq 7\). More precisely, the number of connected components is at least the number of trees of maximum node degree at most four on \(\lfloor\frac{n-5}{3} \rfloor\) nodes.