A randomized embedding algorithm for trees (Q555509)

In the authors' three related algorithms some vertex \(r\) of a given tree \(T\) is designated as the root, so, for every other vertex \(u\in T\) there is a unique path in \(T\) from \(r\) to \(u\); the neighbour of \(u\) on this path is called the parent of \(u\), and all remaining neighbours of \(u\) are the children of \(u\). For example, they formulate Algorithm 1: Start by embedding the root \(r\) at an arbitrary vertex \(f(r)\in V(G)\). As long as \(T\) is not completely embedded, take an arbitrary vertex \(u \in V(T)\) which is already embedded, but whose children are not. If \(f(u)\) has enough neighbours in \(G\) unoccupied by other vertices of \(T\), embed the children of \(u\) by choosing vertices uniformly at random from the available neighbours of \(f(u)\) and continue. Otherwise fail. Theorem 2.1: Let \(\epsilon\leq\frac18\), and let \(G\) be a \(C_4\)-free graph of minimum degree at least \(d\). For any tree \(T\) of order \(| T| \leq\epsilon d^2\) and maximum degree \(\Delta\leq d-2\epsilon d-2\), Algorithm 1 finds an embedding of \(T\) in \(G\) with high probability (i.e., with probability tending to 1 as \(d\to\infty\)). Theorem 3.5: Let \(G\) be a \(K_{s,t}\)-free graph \((s\leq t)\) of minimum degree \(d\). For any tree \(T\) of order \(| T| \leq\frac1{64}s^{-\frac{1}{t-1}}d^{\frac{t}{t-1}}\) and maximum degree \(\Delta\leq\frac d{256}\), Algorithm 2 finds an embedding of \(T\) in \(G\) with high probability. Theorem 4.1:Let \(G\) be a graph with minimum degree \(d\) and girth \(2k+1\). Then, for any constant \(\epsilon\leq\frac1{2k}\), Algorithm 3 succeeds with high probability in embedding (in \(G\)) any tree \(T\) of order \(\frac14\epsilon d^k\) and maximum degree \(\Delta(T)\leq (1-2\epsilon)d-2\).