LeafPower - Maple Help

GraphTheory

 LeafPower
 construct kth leaf power

 Calling Sequence LeafPower(T, k)

Parameters

 T - tree, arborescence, or anti-arborescence k - positive integer

Description

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $T≔\mathrm{Newick}\left("\left(\left(\left(4,5,\left(\left(3\right)2,9\right)7\right)6,10\right)8\right)1;"\right)$
 ${T}{≔}{\mathrm{Graph 1: a directed unweighted graph with 10 vertices and 9 arc\left(s\right)}}$ (1)
 > $\mathrm{LP3}≔\mathrm{LeafPower}\left(T,3\right)$
 ${\mathrm{LP3}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 6 vertices and 9 edge\left(s\right)}}$ (2)
 > $\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\}$ (3)

The path graph on n nodes has only two leaves, the vertices 1 and n. The leaf power is empty unless k >= n-1.

 > $\mathrm{PG}≔\mathrm{PathGraph}\left(5\right)$
 ${\mathrm{PG}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 5 vertices and 4 edge\left(s\right)}}$ (4)
 > $\mathrm{Edges}\left(\mathrm{PG}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{4}{,}{5}\right\}\right\}$ (5)
 > $\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\left(s\right)}}$ (6)
 > $\mathrm{Edges}\left(\mathrm{LP2}\right)$
 ${\varnothing }$ (7)
 > $\mathrm{LP4}≔\mathrm{LeafPower}\left(\mathrm{PG},4\right)$
 ${\mathrm{LP4}}{≔}{\mathrm{Graph 5: an undirected unweighted graph with 2 vertices and 1 edge\left(s\right)}}$ (8)
 > $\mathrm{Edges}\left(\mathrm{LP4}\right)$
 $\left\{\left\{{1}{,}{5}\right\}\right\}$ (9)

Compatibility

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