Graphic and protographic lists of integers

Dmitry Fon-Der-Flaass ; Douglas B. West

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

A positive list (list of positive integers) is protographic if its merger with all but finitely many positive graphic lists is graphic. Define the family ${\cal P}_s$ of $s$-protogaphic lists by letting ${\cal P}_0$ be the family of positive graphic lists and letting ${\cal P}_s$ for $s>0$ be the family of positive lists whose merger with all but finitely many lists in ${\cal P}_{s-1}$ is in ${\cal P}_{s-1}$. The main result is that $X\in{\cal P}_s$ if and only if $t(X)\in {\cal P}_{s-1}$, where $t(X)$ is the list obtained from $X$ by subtracting one from each term of $X$ (deleting those that become $0$) and appending a 1 for each term of $X$. A corollary is that the maximum number of iterations to reach a graphic list from an $n$-term even list with sum $2k$ is $k-n+1$ (when $k\ge n$), achieved by the unique such list having one term larger than 1.

Détail

DOI : 10.37236/1757

Classification : 05C07