Markov Graphs Of One–Dimensional Dynamical Systems And Their Discrete Analogues

Abstract. One feature of the famous Sharkovsky’s theorem is that it can be proved using digraphs of a special type (the so–called Markov graphs). The most general definition assigns a Markov graph to every continuous map from the topological graph to itself. We show that this definition is too broad, i.e. every finite digraph can be viewed as a Markov graph of some one–dimensional dynamical system on a tree. We therefore consider discrete analogues of Markov graphs for vertex maps on combinatorial trees and characterize all maps on trees whose discrete Markov graphs are of the following types: complete, complete bipartite, the disjoint union of cycles, with every arc being a loop