LeafPower(T,k) returns the kth leaf power of a given tree T. This is a graph whose vertices are the leaves of T and in which two vertices are connected if there is a path of length at most k between them in the original tree.

The input graph T may be directed or undirected.

The kth leaf power of T is an induced subgraph of the kth graph power of T.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$T≔\mathrm{Newick}\left(''(((4,5,((3)2,9)7)6,10)8)1;''\right)$

$T≔\mathrm{Graph\; 1:\; a\; directed\; unweighted\; graph\; with\; 10\; vertices\; and\; 9\; arc(s)}$

$\mathrm{LP3}≔\mathrm{LeafPower}\left(T\,3\right)$

$\mathrm{LP3}≔\mathrm{Graph\; 2:\; an\; undirected\; unweighted\; graph\; with\; 6\; vertices\; and\; 9\; edge(s)}$

$\mathrm{Edges}\left(\mathrm{LP3}\right)$

$\left\{\left\{1\,4\right\}\,\left\{1\,5\right\}\,\left\{1\,10\right\}\,\left\{3\,9\right\}\,\left\{4\,5\right\}\,\left\{4\,9\right\}\,\left\{4\,10\right\}\,\left\{5\,9\right\}\,\left\{5\,10\right\}\right\}$

$\mathrm{PG}≔\mathrm{PathGraph}\left(5\right)$

$\mathrm{PG}≔\mathrm{Graph\; 3:\; an\; undirected\; unweighted\; graph\; with\; 5\; vertices\; and\; 4\; edge(s)}$

$\mathrm{Edges}\left(\mathrm{PG}\right)$

$\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\,\left\{3\,4\right\}\,\left\{4\,5\right\}\right\}$

$\mathrm{DrawGraph}\left(\mathrm{PG}\,\mathrm{style}=\mathrm{circle}\right)$

$\mathrm{LP2}≔\mathrm{LeafPower}\left(\mathrm{PG}\,2\right)$

$\mathrm{LP2}≔\mathrm{Graph\; 4:\; an\; undirected\; unweighted\; graph\; with\; 2\; vertices\; and\; 0\; edge(s)}$

$\mathrm{Edges}\left(\mathrm{LP2}\right)$

$\varnothing$

$\mathrm{LP4}≔\mathrm{LeafPower}\left(\mathrm{PG}\,4\right)$

$\mathrm{LP4}≔\mathrm{Graph\; 5:\; an\; undirected\; unweighted\; graph\; with\; 2\; vertices\; and\; 1\; edge(s)}$

$\mathrm{Edges}\left(\mathrm{LP4}\right)$

$\left\{\left\{1\,5\right\}\right\}$

The GraphTheory[LeafPower] command was introduced in Maple 2021.

For more information on Maple 2021 changes, see Updates in Maple 2021.