Leaf realization problem, caterpillar graphs and prefix normal words

Abstract

Given a simple graph $G$ with $n$ vertices and a natural number $i\le n$, let $L_G(i)$ be the maximum number of leaves that can be realized by an induced subtree $T$ of $G$ with $i$ vertices. We introduce a problem that we call the \emph{leaf realization problem}, which consists in deciding whether, for a given sequence of $n+1$ natural numbers $({\ell }_0,{\ell }_1,\dots ,{\ell }_n)$, there exists a simple graph $G$ with $n$ vertices such that ${\ell }_i=L_G(i)$ for $i=0,1,\dots ,n$. We present basic observations on the structure of these sequences for general graphs and trees. In the particular case where $G$ is a caterpillar graph, we exhibit a bijection between the set of the discrete derivatives of the form $(\Delta L_G(i){)}_{1\le i\le n-3}$ and the set of prefix normal words.

arXiv comment27 pages, 10 figures, preprint

References in corpus (3)

• On Prefix Normal Words and Prefix Normal Forms
• A Note on the Characterization of Digraph Sequences
• Fully leafed induced subtrees

Cited by in corpus (5)

• The degree profile and Gini index of random caterpillar trees
• Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• On Infinite Prefix Normal Words
• Saturated Fully Leafed Tree-Like Polyforms and Polycubes