Partitions of complete geometric graphs into plane trees (Q2489020)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Partitions of complete geometric graphs into plane trees
scientific article

    Statements

    Partitions of complete geometric graphs into plane trees (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    16 May 2006
    0 references
    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.
    0 references
    complete graph
    0 references
    convex graph
    0 references
    book embedding
    0 references
    book thickness
    0 references
    crossing family
    0 references

    Identifiers