Partitions of complete geometric graphs into plane trees (Q2489020): Difference between revisions

A geometric graph \(G\) is a pair \((V(G),E(G))\) where \(V(G)\) is a set of points in general position (no three are collinear), and \(E(G)\) is a set of closed segments with end points in \(V(G)\). The elements of \(V(G)\) are vertices and the elements of \(E(G)\) are edges. A geometric graph is plane if no two edges cross. A convex graph is a geometric graph with the vertices in convex position. For a tree \(T\) let \(T'\) be the tree obtained by deleting the leaves and leaf edges for \(T\). A caterpillar is a tree \(T\) such that \(T'\) is a path. A tree \(T\) is symmetric if there exists an edge \(vw\) of \(T\) such that if \(A\) and \(B\) are the components of \(T\diagdown vw\) then there exists an isomorphism between \(A\) and \(B\) that map \(v\) to \(w\). The main result of the paper is the following theorem. Let \(T_1,T_2,\dots,T_n\) be a partition of the edges of the convex complete graph \(K_{2n}\) into plane spanning trees. Then \(T_1,T_2,\dots,T_n\) are symmetric convex caterpillars that are pairwise isomorphic. Conversely, for any symmetric convex caterpillar \(T\) on \(2n\) vertices, the edges of the convex complete graph \(K_{2n}\) can be partitioned into \(n\) plane spanning convex copies of \(T\) that are pairwise isomorphic. Moreover, there is proved a sufficient condition which generalizes the convex case for a complete geometric graph \(K_{2n}\) to have a partition into plane spanning double stars that are pairwise isomorphic.