DISCRETE MARKOV GRAPHS: LOOPS, FIXED POINTS AND MAPS PREORDERING

We study discrete Markov graphs of vertex maps on finite trees. For every such map one can construct a mixed tree of a special type and from its properties derive a connection between the number of loops in the corresponding discrete Markov graph and number of fixed points of the initial map. As a corollary, we obtain that discrete Markov graphs satisfy Seymour’s Second Neighbourhood Conjecture as well as Caccetta- H¨aggkvist Conjecture. We also consider the natural preordering of vertex maps on trees with respect to their discrete Markov graphs and establish some properties of its maximal elements.