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 CaccettaH¨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.