The Leaf Function of Penrose P2 Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914068485373952 |
|---|---|
| author | Porrier, Carole Goupil, Alain Massé, Alexandre Blondin |
| author_facet | Porrier, Carole Goupil, Alain Massé, Alexandre Blondin |
| contents | 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 $L_{P2}(n)$ for any non-negative integer $n$, and the sequence $\left(L_{P2}(n)\right)_{n\in\mathbb{N}}$ is called the leaf function of Penrose P2-graphs. We present exact and recursive formulae for $L_{P2}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_08262 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Leaf Function of Penrose P2 Graphs Porrier, Carole Goupil, Alain Massé, Alexandre Blondin Combinatorics Discrete Mathematics 90C27 (Primary) 52C23 05B45, 05C10 (Secondary) 05C05 68R10 05C30 05C63 05C69 G.2.1; G.2.2 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 $L_{P2}(n)$ for any non-negative integer $n$, and the sequence $\left(L_{P2}(n)\right)_{n\in\mathbb{N}}$ is called the leaf function of Penrose P2-graphs. We present exact and recursive formulae for $L_{P2}(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. |
| title | The Leaf Function of Penrose P2 Graphs |
| topic | Combinatorics Discrete Mathematics 90C27 (Primary) 52C23 05B45, 05C10 (Secondary) 05C05 68R10 05C30 05C63 05C69 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2312.08262 |