Enumerating graph depletions

Abstract

Let $G$ be a simple, connected graph with finite vertex set $V$ and edge set $E$. A depletion of $G$ is a permutation $v_1{v}_2\dots v_n$ of the elements of $V$ with the property that $v_i$ is adjacent to some member of $\{v_1,v_2,\dots ,v_{i-1}\}$ for each $i\ge 2$. Depletions model the spread of a rumor or a disease through a population and are related to heaps. In this paper, we develop techniques for enumerating the depletions of a graph.