Enumerating graph depletions

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 \geq 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.