Counting the Average Size of Markov Graphs

We calculate the average size (i.e. number of arcs) of Markovgraphs for several classes of vertex maps on finite trees. These are include arbitrary maps, permutations, cyclic permutations and the so-called neighbourhood maps. In the latter case we obtain an explicit formula for the size of corresponding Markov graphs and then provide sharp bounds for it in terms of the underlying trees