The Leaf Function of Penrose P2 Graphs

We study a graph-theoretic problem in the Penrose P2-graphs which are the dual graphs of Penrose tilings by kites and darts. Using substitutions, local isomorphism and other properties of Penrose tilings, we construct a family of arbitrarily large induced subtrees of Penrose graphs with the largest possible number of leaves for a given number n of vertices. These subtrees are called fully leafed induced subtrees. We denote their number of leaves LP2(n) for any non-negative integer n, and the sequence (LP2(n))ₙ is called the leaf function of Penrose P2-graphs. We present exact and recursive formulae for LP2(n), as well as an infinite sequence of fully leafed induced subtrees, which are caterpillar graphs. In particular, our proof relies on the construction of a finite graded poset of 3-internal-regular subtrees. 25 pages, 19 figures