A randomized embedding algorithm for trees

Trees (05C05) Extremal problems in graph theory (05C35) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Review text

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\).

Recommendations

Cites work

Cited in

(11)

This page was built for publication: A randomized embedding algorithm for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q555509)