Lower Bounds for Leaf Rank of Leaf Powers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910347186667520 |
|---|---|
| author | Høgemo, Svein |
| author_facet | Høgemo, Svein |
| contents | Leaf powers and $k$-leaf powers have been studied for over 20 years, but there are still several aspects of this graph class that are poorly understood. One such aspect is the leaf rank of leaf powers, i.e. the smallest number $k$ such that a graph $G$ is a $k$-leaf power. Computing the leaf rank of leaf powers has proved a hard task, and furthermore, results about the asymptotic growth of the leaf rank as a function of the number of vertices in the graph have been few and far between. We present an infinite family of rooted directed path graphs that are leaf powers, and prove that they have leaf rank exponential in the number of vertices (utilizing a type of subtree model first presented by Rautenbach [Some remarks about leaf roots. Discrete mathematics, 2006]). This answers an open question by Brandstädt et al. [Rooted directed path graphs are leaf powers. Discrete mathematics, 2010]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18245 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Leaf Rank of Leaf Powers Høgemo, Svein Discrete Mathematics Data Structures and Algorithms Combinatorics G.2.2 Leaf powers and $k$-leaf powers have been studied for over 20 years, but there are still several aspects of this graph class that are poorly understood. One such aspect is the leaf rank of leaf powers, i.e. the smallest number $k$ such that a graph $G$ is a $k$-leaf power. Computing the leaf rank of leaf powers has proved a hard task, and furthermore, results about the asymptotic growth of the leaf rank as a function of the number of vertices in the graph have been few and far between. We present an infinite family of rooted directed path graphs that are leaf powers, and prove that they have leaf rank exponential in the number of vertices (utilizing a type of subtree model first presented by Rautenbach [Some remarks about leaf roots. Discrete mathematics, 2006]). This answers an open question by Brandstädt et al. [Rooted directed path graphs are leaf powers. Discrete mathematics, 2010]. |
| title | Lower Bounds for Leaf Rank of Leaf Powers |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics G.2.2 |
| url | https://arxiv.org/abs/2402.18245 |