The Markov graph of a self-map on a combinatorial tree is a directed graph that encodes the covering relations between edges of the tree under the map. This work explores the dynamical structure of self-maps on trees with weakly connected Markov graphs. The main result of the paper is a complete characterization of self-maps on finite sets that yield weakly connected Markov graphs for all trees. Additionally, we describe the dynamical structure of self-maps whose Markov graphs take specific forms, including complete digraphs, cycles, paths, in-stars, and out-stars.
The simplest example of a discrete dynamical system is a self-map \(f\colon X\to X\) on a set \(X\). Typically, \(X\) has some additional structure (algebraic, topological, graph structure or some other), requiring \(f\) to respect this structure in a natural way. For instance, we can consider endomorphisms on groups, continuous maps on topological spaces, or graph endomorphisms. However, even if the set \(X\) does not possess any inherent structure, the pair \((X, f)\) can still be viewed as an algebraic object (the so-called monounary algebra [8]), or as a topological object (the so-called primal space [5], or functionally Alexandroff space [18]). In both cases, the study of these objects leads to intriguing results and questions, as demonstrated in the corresponding literature.
In this work, we will treat the pairs \((X,f)\) as dynamical systems. A foundational result in the field of combinatorial dynamics is the Sharkovsky theorem, which completely resolves the question of co-existence of periods of periodic points for a continuous map from the unit interval to itself [17]. Remarkably, this theorem can be proved rather in an elementary way by the means of graph theory [7, 19]. Specifically, let \(x\in[0,1]\) be a periodic point of period \(n\) for a continuous map \(f\colon[0,1]\to[0,1]\). It is clear that the orbit \(\mathop{\mathrm{orb}}_{f}(x)=\{x,f(x),\dots,f^{n-1}(x)\}=\{x_{1}<\dots<x_{n}\}\) is a finite set, and the restriction of \(f\) to \(\mathop{\mathrm{orb}}_{f}(x)\) is a cyclic permutation. The corresponding periodic digraph \(\Gamma\) has the vertex set \(\{1,\dots,n-1\}\), and there is an arc \(i\to j\) if \(\min\{f(x_{i}),f(x_{i+1})\leq j<\max\{f(x_{i}),f(x_{i+1})\}\). In other words, the vertices of \(\Gamma\) correspond to the minimal intervals \([x_{i},x_{i+1}]\), and the arcs encode when \([x_{i},x_{i+1}]\) surely “covers” \([x_{j},x_{j+1}]\) under \(f\) (meaning that \([x_{j},x_{j+1}]\subset f([x_{i},x_{i+1}])\)). It turns out that studying cycles in periodic digraphs provides significant insights about periodic points of the corresponding map.
From a graph-theoretic perspective, periodic digraphs are constructed from the undirected \(n\)-path \(X\) and its cyclic permutation \(\sigma\). By extending this idea to arbitrary finite trees \(X\) and their not necessarily bijective maps \(\sigma\), we arrive at the definition of Markov graphs. Similar reasoning as in [7, 19] can be employed to obtain analogues of the Sharkovsky theorem for continuous vertex self-maps on topological trees [2].
In the note [20], Szigeti considered the following “inverse question” for endomorphisms of lattices: given a map \(f\colon X \to X\) on a set \(X\), under what conditions does there exist a lattice structure on \(X\) such that \(f\) is an endomorphism? The subsequent work of Foldes and Szigeti [6] extends this inquiry to lattice anti-endomorphisms. Additionally, the papers [4, 3] describe the dynamical structure of automorphisms of abelian groups, as well as automorphisms of the groups \(\mathbb{Z}^{n}\) and \(\mathbb{Z}^{n}_{p}\) for prime numbers \(p\). In this paper, we explore a similar inverse question for maps on combinatorial trees that produce weakly connected Markov graphs.
The paper is organized as follows. In Section 2, we provide the necessary definitions and preliminary results on graphs, digraphs, maps on trees, and Markov graphs. Section 3.1 describes the self-maps \(\sigma\colon V\to V\) on finite sets \(V\) that produce weakly connected Markov graphs for some (or for all) trees on \(V\) (see Proposition 3.1 and Theorem 3.4). In Section 3.2 we present complete descriptions of the dynamical structure of maps \(\sigma\colon V\to V\) that admit trees \(X\) on \(V\) with Markov graphs \(\Gamma(X,\sigma)\) that are complete digraphs, cycles, paths, in-stars, and out-stars (see Propositions 3.8– 3.13).
In this paper, all graphs, digraphs and sets are assumed to be finite.
An undirected graph, or simply a graph is a pair \(G=(V,E)\), where \(V=V(G)\) is the set of its vertices and \(E=E(G)\) is the set of its edges (which are unordered pairs of vertices). We note that all our graphs are simple, meaning that they do not have multiple edges or loops.
The existence of an edge \(\{u,v\}\in E(G)\) in a graph \(G\) will be denoted simply as \(uv\in E(X)\). The set \(N_{G}(u)=\{v\in V(G):uv\in E(G)\}\) is called the neighborhood of a vertex \(u\in V(G)\). Similarly, by \(E_{G}(u)\) we denote the set of edges incident with \(u\).
For a set of vertices \(S \subset V(G)\), the corresponding induced subgraph is denoted by \(G[S]\), where \(V(G[S]) = S\) and \(E(G[S]) = \{uv \in E(G): u,v \in S\}\). We will also use the notation \(E_{G}(S)\) to refer to \(E(G[S])\).
An isomorphism between two graphs \(G\) and \(H\) is a bijective map \(f\colon V(G)\to V(H)\) that preserves the edges in both ways: \(uv\in E(G)\) if and only if \(f(u)f(v)\in E(H)\). An isomorphism from a graph \(G\) to itself is called an automorphism of \(G\).
A graph is connected if there is a path between every pair of its vertices. The following folklore characterization of connected graphs is particularly useful.
Proposition 2.1. A graph \(G\) is connected if and only if for any proper partition \(V(G)=A\sqcup B\) (here \(A,B\neq\emptyset\)), there exist two vertices \(a\in A\) and \(b\in B\) with \(ab\in E(G)\).
A set of vertices \(A\subset V(G)\) is connected provided the induced subgraph \(G[A]\) is connected.
Each maximal connected subgraph of a given graph is called its connected component. A cut-vertex is a vertex whose removal increases the number of connected components in a graph.
The vertex set \(V(G)\) of a connected graph \(G\) is endowed with the graph metric \(d_{G}\), where \(d_{G}(u,v)\) equals the length of a shortest \(u-v\) path in \(G\). For a vertex \(u\in V(G)\) and a set \(S\subset V(G)\), by \(d_{G}(u,S)=\min\{d_{G}(u,x):x\in S\}\) we denote the distance from \(u\) to \(S\).
The metric interval between a pair of vertices \(u,v\in V(G)\) is the set \([u,v]_{G}=\{x\in V(G):d_{G}(u,x)+d_{G}(x,v)=d_{G}(u,v)\}\). A set of vertices \(S\subset V(G)\) is convex provided \([a,b]_{X}\subset S\) for all \(a,b\in S\). The convex hull \(\mathop{\mathrm{Conv}}_{G}(A)\) of a set \(A\subset V(G)\) is the smallest convex set containing \(A\), meaning that \(\mathop{\mathrm{Conv}}_{G}(A)\) is the intersection of all such convex sets.
For an edge \(uv\in E(G)\), the sets \(W_{G}(u,v)=\{x\in V(G):d_{G}(u,x)<d_{G}(v,x)\}\) and \(W_{G}(v,u)=\{x\in V(G):d_{G}(v,x)<d_{G}(u,x)\}\) are called half-spaces.
A forest is just an acyclic graph. A tree is a connected forest. Hence, each forest consists of disjoint trees. A vertex of degree \(1\) is called a leaf. For a tree \(X\), by \(\mathop{\mathrm{Leaf}}(X)\) we denote the set of leaf vertices in \(X\). A path is a tree \(X\) with \(|\mathop{\mathrm{Leaf}}(X)|\leq 2\). A star is a tree \(X\) with \(|\mathop{\mathrm{Leaf}}(X)|\geq|V(X)|-1\). If \(X\) is a star with \(|\mathop{\mathrm{Leaf}}(X)|=|V(X)|-1\), then the unique non-leaf vertex in \(X\) will be called the center of \(X\).
For a given set \(V\), by \(\mathop{\mathrm{Tr}}(V)\) we denote the class of all trees \(X\) with the vertex set \(V(X)=V\).
A directed graph, or just a digraph is a pair \(D=(V,A)\), where \(V=V(D)\) is the set of its vertices and \(A=A(D)\subset V\times V\) is the set of its arcs. For convenience, an arc \((u, v) \in A(D)\) will also be denoted as \(u \rightarrow v\). An arc of the form \(u\rightarrow u\) in a digraph \(D\) is called a loop at the vertex \(u\). Note that, aside from loops, our digraphs may also have cycles of length \(2\).
A digraph \(D\) is called empty if \(A(D)=\emptyset\), and it is complete provided \(A(D)=V(D)\times V(D)\).
The out-neighborhood of a vertex \(u\in V(D)\) is the set \(N_{D}^{+}(u)=\{v\in V(D):(u,v)\in A(D)\}\). Its cardinality \(d_{D}^{+}(u)=|N_{D}^{+}(u)|\) is called the out-degree of \(u\).
A vertex \(v\in V(D)\) is reachable from a vertex \(u\in V(D)\), if there is a path from \(u\) to \(v\) in \(D\), i.e., there exist vertices \(x_{1},\dots,x_{m}\in V(D)\) such that \(u\rightarrow x_{1}\rightarrow\dots\rightarrow x_{m}\rightarrow v\). By definition, a vertex is always reachable from itself.
A digraph \(D\) is called weakly connected if the corresponding undirected graph (obtained from \(D\) by ignoring orientations of arcs, loops, and \(2\)-cycles) is connected. The next characterization of weak connectedness immediately follows from Proposition 2.1.
Corollary 2.2. A digraph \(D\) is weakly connected if and only if, for any proper partition \(V(D)=A\sqcup B\) (here \(A,B\neq\emptyset\)), there exist \(a\in A\) and \(b\in B\) such that either \(a\) is reachable from \(b\) or \(b\) is reachable from \(a\).
A weak component in a digraph \(D\) is its maximal weakly connected subdigraph.
Let \(V\) be a finite set. By \(\mathcal{T}(V)\), we denote the full transformation semigroup on \(V\), i.e., the class of all self-maps \(\sigma\colon V\to V\). Similarly, \(\mathcal{S}(V)\) denotes the symmetric group on \(V\), i.e., the class of all permutations of \(V\). The identity map on \(V\) is denoted by \(\mathop{\mathrm{id}}_{V}\). The image of a map \(\sigma \in \mathcal{T}(V)\) is denoted by \(\mathop{\mathrm{Im}}\sigma\). A map \(\sigma\) is called constant if \(|\mathop{\mathrm{Im}}\sigma| = 1\).
Throughout the paper we will use the following standard notation for self-maps on finite sets: if \(V=\{1,\dots,n\}\) and \(\sigma\in\mathcal{T}(V)\), then we write \(\sigma=\left( \begin{array}{cccc} 1 & 2 & \dots & n\\ \sigma(1) & \sigma(2) & \dots & \sigma(n)\\ \end{array}\right)\). Since any permutation can be represented as the product of pairwise disjoint cycles, this notation will be simplified for permutations as follows: for example, if \(V=\{1,\dots,9\}\) and \(\sigma=\left( \begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 5 & 1 & 2 & 4 & 3 & 8 & 9 & 6 & 7\\ \end{array}\right)\), then we will write \(\sigma=(1532)(4)(68)(79)\).
An element \(x\in V\) is called a fixed point for a map \(\sigma\in\mathcal{T}(V)\) if \(\sigma(x)=x\). The set of all fixed points of \(\sigma\) is denoted by \(\mathop{\mathrm{fix}}\sigma\). An element \(x\in V\) is called a \(\sigma\)-periodic point if there exists \(m\in\mathbb{N}\) with \(\sigma^{m}(x)=x\). The smallest such \(m\) is called the period of \(x\). Therefore, fixed points are precisely \(\sigma\)-periodic points with period \(1\). We denote the set of all \(\sigma\)-periodic points by \(\mathop{\mathrm{per}}\sigma\).
The set \(\mathop{\mathrm{orb}}_{\sigma}(x) = \{x,\sigma(x),\sigma^2(x),\dots,\sigma^n(x),\dots\}\) is called the orbit of \(x\). A set \(A \subset V\) is called \(\sigma\)-invariant if \(\sigma(A) \subset A\). For example, the orbit \(\mathop{\mathrm{orb}}_{\sigma}(x)\) of any element \(x \in V\) is always a \(\sigma\)-invariant set. Note also that, by finitness of \(V\), every non-empty \(\sigma\)-invariant set contains at least one \(\sigma\)-periodic point.
Let \(X\) be a tree and \(\sigma\colon V(X)\to V(X)\) be some map. The Markov graph is a directed graph \(\Gamma=\Gamma(X,\sigma)\) with the vertex set \(V(\Gamma)=E(X)\) and the arc set \[A(\Gamma)=\{(u_{1}v_{1},u_{2}v_{2})\in E(X)\times E(X):u_{2},v_{2}\in[\sigma(u_{1}),\sigma(v_{1})]_{X}\}.\] In other words, \(N_{\Gamma}^{+}(uv)=E_{X}([\sigma(u),\sigma(v)]_{X})\) for all edges \(uv\in E(X)\).
Example 2.3. Let \(X\) be a tree with the vertex set \(V(X)=\{1,\dots,8\}\) and the edge set \(E(X)=\{12,23,34,45,26,37,38\}\). Consider the map \[\sigma=\left( \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 6 & 7 & 6 & 2 & 3 & 3 & 5 & 4 \\ \end{array}\right),\] from \(V(X)\) to itself. Then the corresponding Markov graph \(\Gamma(X,\sigma)\) is depicted in Figure 1.
The following lemma provides a simple but quite useful tool for proving the existence of arcs in Markov graphs.
Lemma 2.4. [10, Lemma 3.17] Let \(X\) be a tree and \(\sigma\colon V(X)\to V(X)\) be a map. Then for every pair of vertices \(u,v\in V(X)\) and an edge \(e\in E_{X}([\sigma(u),\sigma(v)]_{X})\), there exists an edge \(e'\in E_{X}([u,v]_{X})\) with \(e'\rightarrow e\) in \(\Gamma(X,\sigma)\).
Using Lemma 2.4 and a straightforward induction argument, we can obtain the next technical corollary on reachability between vertices in Markov graphs.
Corollary 2.5. Let \(X\) be a tree, \(\sigma\colon V(X)\to V(X)\) be a map, and \(k\in\mathbb{N}\). Then for every pair of vertices \(u,v\in V(X)\) and an edge \(e\in E_{X}([\sigma^{k}(u),\sigma^{k}(v)]_{X})\), there exists an edge \(e'\in E_{X}([u,v]_{X})\) such that \(e\) is reachable from \(e'\) in \(\Gamma(X,\sigma)\).
We also note that one can characterize several classes of self-maps on trees in terms of the properties of their Markov graphs. For example, for tree automorphisms, the next result holds.
Proposition 2.6. [10, Proposition 3.15]Let \(X\) be a tree and \(\sigma:V(X)\to V(X)\) be a map. Then \(\sigma\) is an automorphism of \(X\) if and only if the Markov graph \(\Gamma(X,\sigma)\) is a disjoint union of cycles.
As we have mentioned before, our digraphs can have loops. In \(\Gamma(X,\sigma)\), there is a loop at \(uv\in E(X)\) if and only if the images \(\sigma(u)\) and \(\sigma(v)\) lie in different half-spaces \(W_{G}(u,v)\) and \(W_{G}(v,u)\). Thus, there are two types of loops in Markov graphs. Namely, an edge \(uv\in E(X)\) is called \(\sigma\)-positive (\(\sigma\)-negative) if \(\sigma(u)\in W_{G}(u,v)\) and \(\sigma(v)\in W_{G}(v,u)\) (\(\sigma(u)\in W_{G}(v,u)\) and \(\sigma(v)\in W_{G}(u,v)\)). For example, the Markov graph in Figure 1 has a unique loop at \(23\), which is a \(\sigma\)-negative edge.
By \(p(X,\sigma)\) and \(n(X,\sigma)\) we denote the numbers of \(\sigma\)-positive and \(\sigma\)-negative edges, respectively. These numbers are connected by the following equality.
Theorem 2.7. [9, Theorem 4.2]For any tree \(X\) and a map \(\sigma\colon V(X)\to V(X)\), it holds that \(n(X,\sigma)+|\mathop{\mathrm{fix}}\sigma|=p(X,\sigma)+1\).
First, we demonstrate that, with the exception of two trivial classes of maps, any map \(\sigma\in\mathcal{T}(V)\) admits a tree \(X\in\mathop{\mathrm{Tr}}(V)\) with a weakly connected Markov graph \(\Gamma(X,\sigma)\).
Proposition 3.1. Let \(n=|V|\geq 3\). Then for a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is weakly connected if and only if \(\sigma\) is neither a constant map nor the identity map on \(V\).
Proof. Necessity. This is trivial because any constant map has an empty Markov graph, and the Markov graph \(\Gamma(X,\mathop{\mathrm{id}}_{V})\) is just a disjoint union of loops. Hence, in both cases, \(\Gamma(X,\sigma)\) is disconnected (as \(n\geq 3\) implies that \(\Gamma(X,\sigma)\) has \(|E(X)|\geq 2\) vertices).
Sufficiency. Since \(\sigma\neq\mathop{\mathrm{id}}_{V}\), there is \(u\in V\) with \(\sigma(u)\neq u\). And since \(\sigma\) is not constant, there is \(v\in V\) with \(\sigma(u)\neq\sigma(v)\). We consider three separate cases for the elements \(\sigma(u)\) and \(\sigma(v)\).
Case 1. \(\sigma(u)\neq v\) and \(\sigma(v)\neq u\).
In this case, for any path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(uv\in E(X)\), the Markov graph \(\Gamma(X,\sigma)\) is weakly connected.
Case 2. \(\sigma(u)=v\) and \(\sigma(v)\neq u\) (similarly, we can consider the case where \(\sigma(u)\neq v\) and \(\sigma(v)=u\)).
In this case, for any path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(uv\in E(X)\) and \(\mathop{\mathrm{Leaf}}(X)=\{v,\sigma(v)\}\), the Markov graph \(\Gamma(X,\sigma)\) is weakly connected.
Case 3. \(\sigma(u)=v\) and \(\sigma(v)=u\).
Since \(n\geq 3\), the set \(V\setminus\{u,v\}\) is non-empty. If \(V\setminus\{u,v\}=\mathop{\mathrm{fix}}\sigma\), then for any path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(\mathop{\mathrm{Leaf}}(X)=\{u,v\}\), the Markov graph \(\Gamma(X,\sigma)\) is weakly connected. Hence, assume that \(\sigma(x)\neq x\) for some \(x\in V\setminus\{u,v\}\). Without loss of generality, \(\sigma(x)\neq v\) (similarly, we can consider the case where \(\sigma(x)\neq u\)). In this case, for any path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(ux\in E(X)\) and \(\mathop{\mathrm{Leaf}}(X)=\{v,\sigma(x)\}\), the Markov graph \(\Gamma(X,\sigma)\) is also weakly connected. ◻
To characterize maps \(\sigma\) that produce weakly connected Markov graphs for all trees on \(V\), we need several new definitions. A permutation \(\sigma\in\mathcal{S}(V)\) is called circular of length \(m\) [1, p. 120] if \(\sigma\) has exactly \(n-m\) fixed points, and it cyclically permutes the set \(V\setminus\mathop{\mathrm{fix}}\sigma\). For example, a circular permutation of length \(n\) is just a plain cyclic permutation. Further, a map \(\sigma\in\mathcal{T}(V)\) is called nilpotent if, for some \(k\in\mathbb{N}\), the \(k\)-th iterate map \(\sigma^{k}\) is constant. A nilpotent map \(\sigma\in\mathcal{T}(V)\) will be called path-nilpotent provided \(|\sigma^{-1}(x)\setminus\{x\}|=1\) for all \(x\in\mathop{\mathrm{Im}}\sigma\).
Example 3.2. Let \(V=\{1,\dots,8\}\). Then the permutation \(\sigma_{1}=(123456)(7)(8)\) is circular of length \(6\); the map \(\sigma_{2}=\left( \begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 2 & 2 & 2 & 7 & 3 & 4 & 2 \\ \end{array}\right)\) is nilpotent with \(\mathop{\mathrm{fix}}\sigma_{2}=\{2\}\); and the map \(\sigma_{3}=\left( \begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \end{array}\right)\) is path-nilpotent with \(\mathop{\mathrm{fix}}\sigma_{3}=\{1\}\).
Before presenting the main result of this paper, we will need one supplementary result. Let us say that a set \(A\subset V(X)\) in a tree \(X\) is good if \(A\) is connected and all the edges from \(E_{X}(A)\) lie in a common weak component in \(\Gamma(X,\sigma)\).
Lemma 3.3 Let \(X\) be a tree and \(A\subset V(X)\) be a good set which contains a \(\sigma\)-negative edge. Then the set \(\mathop{\mathrm{Conv}}_{X}(A\cup\sigma(A))\) is also good.
Proof. First, we observe that \(\mathop{\mathrm{Conv}}_{X}(A\cup\sigma(A))=A\cup\{[a,\sigma(a)]_{X}:a\in A\}\). Indeed, on the one hand, the convex hull of \(A\cup\sigma(A)\) must contain all the intervals \([a,\sigma(a)]_{X}\) for \(a\in A\). On the other hand, the set \(A\cup\{[a,\sigma(a)]_{X}:a\in A\}\) is connected, and since \(X\) is a tree, this implies it is convex.
Now let \(uv\in E_{X}(A)\) be a \(\sigma\)-negative edge. Fix \(a\in A\). If \(a=u\) or \(a=v\), then the edges from \([a,\sigma(a)]_{X}\) clearly lie in the same connected component of \(\Gamma(X,\sigma)\) as the edges from \(E_{X}(A)\). Otherwise, assume \(a\in A\setminus\{u,v\}\). Without loss of generality, suppose \(a\in W_{X}(u,v)\).
If \(\sigma(a)\in W_{X}(u,v)\), then (see Figure 2); \[[a,\sigma(a)]_{X}\subset[a,u]_{X}\cup[u,\sigma(a)]_{X}\subset[a,u]_{X}\cup[\sigma(u),\sigma(a)]_{X}.\]
And since \([a,u]_{X}\subset A\) (as \(A\) is connected), we conclude that every edge inside \([a,\sigma(a)]_{X}\) lies in a common weak component in \(\Gamma(X,\sigma)\) as the edges from \(E_{X}([a,u]_{X})\neq\emptyset\).
Similarly, if \(\sigma(a)\in W_{X}(v,u)\), then (see Figure 3); \[[a,\sigma(a)]_{X}\subset[a,v]_{X}\cup[v,\sigma(a)]_{X}\subset[a,v]_{X}\cup[\sigma(v),\sigma(a)]_{X}.\]
In this case, the edges within \([a,\sigma(a)]_{X}\) lie in the same weak component in \(\Gamma(X,\sigma)\) as the edges from \(E_{X}([a,v]_{X})\neq\emptyset\). In both cases, edges from \(E_{X}([a,\sigma(a)]_{X})\) share the same weak component as those from \(E_{X}(A)\). Therefore, \(\mathop{\mathrm{Conv}}_{X}(A\cup\sigma(A))\) is also a good set. ◻
Now we are ready to completely describe the dynamical structure of maps producing weakly connected Markov graphs for all trees.
Theorem 3.4. Let \(n=|V|\geq 2\). For a map \(\sigma\in\mathcal{T}(V)\), the Markov graph \(\Gamma(X,\sigma)\) is weakly connected for all trees \(X\in\mathop{\mathrm{Tr}}(V)\) if and only if \(\sigma\) satisfies one of the following conditions:
(a) \(\sigma\) is a path-nilpotent map;
(b) \(\sigma\) is a circular permutation of length \(n-1\);
(c) \(\sigma\) is a permutation, and the periods of \(\sigma\)-periodic points with disjoint orbits are pairwise incomparable under division.
Proof. Necessity. Let \(\Gamma(X,\sigma)\) be weakly connected for all trees \(X\in\mathop{\mathrm{Tr}}(V)\). We split the argument into a series of claims.
Claim 1. If \(\sigma\) is not a permutation, then \(\sigma\) is path-nilpotent.
Since \(\sigma\notin\mathcal{S}(V)\), we have \(V\setminus\mathop{\mathrm{Im}}\sigma\neq\emptyset\). Consider the map \(f\colon V\setminus\mathop{\mathrm{Im}}\sigma\to\mathbb{N}\), where \[f(x)=\min\{k\in\mathbb{N}:|\sigma^{-1}(\sigma^{k}(x))|\geq 2\},\] for \(x\in V\setminus\mathop{\mathrm{Im}}\sigma\). Fix an element \(x_{0}\in V\setminus\mathop{\mathrm{Im}}\sigma\) that minimizes \(f\), i.e., \(f(x_{0})=\min\{f(x):x\in V\setminus\mathop{\mathrm{Im}}\sigma\}\). Consider the set \[V'=V\setminus\{\sigma^{i}(x_{0}):0\leq i\leq f(x_{0})-1\}.\]
By construction, the restriction \(\sigma '=\sigma|_{V'}\) is a self-map on \(V'\).
If the element \(\sigma^{f(x_{0})}(x_{0})\) is a fixed point for \(\sigma\), then consider the star \(X\in\mathop{\mathrm{Tr}}(V)\) centered at \(\sigma^{f(x_{0})}(x_{0})\). The edge set \(\{\sigma^{f(x_{0})}(x_{0})\sigma^{i}(x_{0}):0\leq i\leq f(x_{0})-1\}\) induces a weak component in \(\Gamma(X,\sigma)\) (specifically, a path of length \(f(x_{0})-1\)). This means that \(V'=\{\sigma^{f(x_{0})}(x_{0})\}\), which implies that \(\sigma\) is path-nilpotent in this case.
Now assume that \(\sigma^{f(x_{0})}(x_{0})\) is not a fixed point for \(\sigma\). Note that in this case, \(|V'|\geq 2\) (since \(\sigma^{f(x_{0})}(x_{0})\) and \(\sigma^{f(x_{0})+1}(x_{0})\) are two different elements of \(V'\)). Since \(|\sigma^{-1}(\sigma^{f(x_{0})}(x_{0}))|\geq 2\), there exists \(y\in\sigma^{-1}(\sigma^{f(x_{0})}(x_{0}))\setminus\{\sigma^{f(x_{0})-1}(x_{0})\}\).
We aim to show that \[\sigma^{-(f(x_{0})-1)}(y)\cap V'\neq\emptyset.\]
First, assume \(y\in\mathop{\mathrm{per}}\sigma\) is a \(\sigma\)-periodic point. Then \(\sigma^{f(x_{0})}(x_{0})=\sigma(y)\) is also \(\sigma\)-periodic. And since \(\mathop{\mathrm{orb}}_{\sigma}(y)=\mathop{\mathrm{orb}}_{\sigma}(\sigma^{f(x_{0})}(x_{0}))\), it is clear that \(\mathop{\mathrm{orb}}_{\sigma}(y)\) cannot share elements with the set \(\{\sigma^{i}(x_{0}):0\leq i\leq f(x_{0})-1\}\). Hence, \(\mathop{\mathrm{orb}}_{\sigma}(y)\subset V'\). Therefore, in this case, \(\sigma^{-k}(y)\cap V'\neq\emptyset\) for all \(k\geq 1\).
Second, suppose \(y\) is not \(\sigma\)-periodic. For the sake of contradiction, assume that \[g(y):=\max\{k\in\mathbb{N}\cup\{0\}:\sigma^{-k}(y)\neq\emptyset\}<f(x_{0})-1.\]
Fix an element \(z\in\sigma^{-g(y)}(y)\). Clearly, \(z\in V\setminus\mathop{\mathrm{Im}}\sigma\). But then \(f(z)\leq g(y)+1<f(x_{0})\), which contradicts the minimality of \(f(x_{0})\). Hence, we must have \(g(y)\geq f(x_{0})\), which implies \(\sigma^{-(f(x_{0})-1)}(y)\neq\emptyset\). Moreover, since \(y\neq\sigma^{f(x_{0})-1}(x_{0})\), it follows that \(\sigma^{-(f(x_{0})-1)}(y)\subset V'\).
Thus, we can fix an element \(z\in\sigma^{-(f(x_{0})-1)}(y)\cap V'\), and consider an arbitrary tree \(X'\in\mathop{\mathrm{Tr}}(V')\). Construct a graph \(X\) on \(V\) with the edge set \[E(X)=E(X')\cup\{\sigma^{i}(z)\sigma^{i}(x_{0}):0\leq i\leq f(u_{0})-1\}.\]
One can observe that \(X\in\mathop{\mathrm{Tr}}(V)\) is a tree on \(V\) since \(X\) is obtained from the tree \(X'\) by adding several leaf vertices. Furthermore, the edge set \(\{\sigma^{i}(z)\sigma^{i}(x_{0}):0\leq i\leq f(u_{0})-1\}\) induces a proper (since \(|V'|\geq 2\)) weak component (specifically, a path of length \(f(x_{0})-1\)) in \(\Gamma(X,\sigma)\), which is a contradiction.
Claim 2. \(|\mathop{\mathrm{fix}}\sigma|\leq 1\).
To the contrary, assume \(|\mathop{\mathrm{fix}}\sigma|\geq 2\). Choose two distinct fixed points \(u,v\in\mathop{\mathrm{fix}}\sigma\) and consider a graph \(X\) on \(V\) with the edge set \[E(X)=\left\{ux:x\in\bigcup_{k=1}^{+\infty}\sigma^{-k}(u)\right\}\cup\left\{uv\right\}\cup\left\{vy:y\in V\setminus\bigcup_{k=1}^{+\infty}\sigma^{-k}(u)\right\}.\]
It is easy to see that \(X\in\mathop{\mathrm{Tr}}(V)\) is a tree (the so-called bi-star) in which the edge \(uv\) induces a weak component in \(\Gamma(X,\sigma)\). Since \(n\geq 3\), we have \(|E(X)|\geq 2\), and the Markov graph \(\Gamma(X,\sigma)\) is disconnected. The obtained contradiction proves the claim.
Claim 3. If \(|\mathop{\mathrm{fix}}\sigma|=1\) and \(\sigma\) is a permutation, then \(\sigma\) is circular of length \(n-1\).
Suppose \(\mathop{\mathrm{fix}}\sigma=\{u\}\). Consider the star \(X\in\mathop{\mathrm{Tr}}(V)\) centered at \(u\). Since \(\sigma\) is a permutation of \(V\), it is an automorphism of \(X\). However, \(\Gamma(X,\sigma)\) is weakly connected, implying that \(\Gamma(X,\sigma)\) is a cycle (see Proposition 2.6). Thus, \(\sigma\) cyclically permutes the set of leaf vertices \(\mathop{\mathrm{Leaf}}(X)=V\setminus\{u\}\). Therefore, \(\sigma\) is circular of length \(n-1\).
Claim 4. If \(\mathop{\mathrm{fix}}\sigma=\emptyset\), then \(\sigma\) is a permutation, and the periods of \(\sigma\)-periodic points with disjoint orbits are pairwise incomparable under division.
Let \(\mathop{\mathrm{fix}}\sigma=\emptyset\). The fact that \(\sigma\) is a permutation follows easily from Claim 1.
Now, suppose to the contrary that there exists an element \(u\in V\) with period \(m\) and another element \(v\in V\setminus\mathop{\mathrm{orb}}_{\sigma}(u)\) with period \(k\) such that \(m\) divides \(k\). Fix any tree \(X'\in\mathop{\mathrm{Tr}}(V\setminus\mathop{\mathrm{orb}}_{\sigma}(v))\) and consider a graph \(X\) on \(V\) with the edge set \[\begin{aligned} E(X)&=E(X')\cup\left(\bigcup_{i=0}^{m-1}\{\sigma^{i}(u)\sigma^{i+mj}(v):0\leq j\leq\frac{k}{m}-1\}\right). \end{aligned}\] One can easily observe that \(X\in\mathop{\mathrm{Tr}}(V)\) is a tree on \(V\) (as \(X\) is obtained from \(X'\) by adding several leaf vertices). Moreover, the edge set \(\bigcup_{i=0}^{m-1}\{\sigma^{i}(u)\sigma^{i+mj}(v):0\leq j\leq\frac{k}{m}-1\}\) induces a proper weak component (a cycle of length \(k\)) in \(\Gamma(X,\sigma)\), which is a contradiction.
Combining Claims 1–4, we can conclude that \(\sigma\) must satisfy one of the conditions 1–3 of the theorem.
Sufficiency. We consider these three conditions separately.
Case 1. \(\sigma\) is path-nilpotent.
In this case, there is a linear ordering of \(V=\{u_{0},\dots,u_{n-1}\}\) with \(\sigma(u_{i})=u_{i-1}\) for \(1\leq i\leq n-1\), and \(\sigma(u_{0})=u_{0}\).
Fix a tree \(X\in\mathop{\mathrm{Tr}}(V)\). We establish the weak connectedness of \(\Gamma(X,\sigma)\) using two claims.
Claim 5. Any two edges from \(E_{X}(u_{0})\) lie in the same weak component in \(\Gamma(X,\sigma)\).
Consider the number \(m:=\max\{i:u_{i}\in N_{X}(u_{0})\}\). Then any edge \(e\in E_{X}(u_{0})\) is reachable from the edge \(u_{0}u_{m}\) in \(\Gamma(X,\sigma)\). To demonstrate this, we use Corollary 2.5. For any \(u_{i}\in N_{X}(u_{0})\) we have \(\sigma^{m-i}(u_{m})=u_{i}\). Also, trivially, \(\sigma^{m-i}(u_{0})=u_{0}\). Thus, there is an arc \(u_{0}u_{m}\rightarrow u_{0}u_{i}\) in \(\Gamma(X,\sigma^{m-i})\). Hence, Corollary 2.5 asserts that \(u_{0}u_{i}\) is reachable from \(u_{0}u_{m}\) in \(\Gamma(X,\sigma)\).
Claim 6. Any edge from \(E(X)\) lies in the same weak component with some edge from \(E_{X}(u_{0})\).
Let \(e=u_{j}u_{k}\in E(X)\) be an arbitrary edge in \(X\). We will prove by induction on \(d_{X}(u_{0},e)\geq 0\) that \(e\) lie in a common weak component with some edge from \(E_{X}(u_{0})\). Without loss of generality, assume \(u_{j}\in[u_{0},u_{k}]_{X}\), thus \(d_{X}(u_{0},e)=d_{X}(u_{0},u_{j})\). For the induction basis, set \(d_{X}(u_{0},u_{j})=0\). Then \(j=0\), implying \(e\in E_{X}(u_{0})\), and we are done.
For the induction step, assume \(d_{X}(u_{0},u_{j})\geq 1\). Below we consider two subcases.
Subcase 1.1. \(k>j\).
In this subcase, we have \(\sigma^{j}(u_{k})=u_{k-j}\) and \(\sigma^{j}(u_{j})=u_{0}\). Thus, by Corollary 2.5, each edge from \(E_{X}([u_{0},u_{k-j}]_{X})\) is reachable from \(e\) in \(\Gamma(X,\sigma)\).
If \(k-j\geq j\), then \(\sigma^{k-j}(u_{k})=u_{j}\) and \(\sigma^{k-j}(u_{j})=u_{0}\). This means that the edge \(e\) reaches all the edges from the interval \([u_{0},u_{j}]_{X}\) (see Figure 4), which are, by induction assumption, lie in a common weak component with some edge from \(E_{X}(u_{0})\). Hence, \(e\) lies in the same weak component of \(\Gamma(X,\sigma)\).
Similarly, if \(k-j<j\), then \(k-j\neq 0\), meaning that the interval \([u_{0},u_{k-j}]_{X}\) contains at least one edge. Further, we have \(\sigma^{2j-k}(u_{j})=u_{k-j}\), which implies that each edge inside \([u_{0},u_{k-j}]_{X}\) is reachable from some edge from \([u_{0},u_{j}]\). Hence, we can fix an edge \(e'\in E_{X}([u_{0},u_{j}])\) which reaches some edge from \(E_{X}([u_{0},u_{k-j}]_{X})\) (see Figure 5). Recalling that each edge from \(E_{X}([u_{0},u_{k-j}]_{X})\) is also reachable from \(e\), we conclude that \(e\) and \(e'\) lie in the same weak component in \(\Gamma(X,\sigma)\). However, \(d_{X}(u_{0},e')<d_{X}(u_{0},e)\), meaning that by induction assumption, \(e'\) lies in a common weak component with some edge \(e''\in E_{X}(u_{0})\). Therefore, \(e\) and \(e''\) also lie in a common weak component in \(\Gamma(X,\sigma)\).
Subcase 1.2. \(k<j\).
Here we use similar reasoning as in the subcase above. It is clear that \(k-j\neq 0\), meaning that the interval \([u_{0},u_{j-k}]_{X}\) contains at least one edge. Also, \(\sigma^{k}(u_{j})=u_{j-k}\) and \(\sigma^{k}(u_{k})=u_{0}\). Hence, by Corollary 2.5, each edge in \(E_{X}([u_{0},u_{j-k}]_{X})\) is reachable from \(e\). Additionally, the equalities \(\sigma^{k}(u_{j})=u_{j-k}\) and \(\sigma^{j-k}(u_{0})=u_{0}\) imply that each edge inside \([u_{0},u_{j-k}]_{X}\) is reachable from some edge in \([u_{0},u_{j}]_{X}\). Hence, we can fix an edge \(e'\in E_{X}([u_{0},u_{j}]_{X})\) which reaches some edge from \(E_{X}([u_{0},u_{j-k}]_{X})\) (see Figure 6). It is clear that \(d_{X}(u_{0},e')<d_{X}(u_{0},e)\). Thus, by induction assumption, \(e'\) lies in a common weak component with some edge \(e''\in E_{X}(u_{0})\). Thus again, \(e\) and \(e''\) lie in a common weak component in \(\Gamma(X,\sigma)\).
Combining Claims 5 and 6, we see that any two edges in \(X\) lie in the same weak component in \(\Gamma(X,\sigma)\), implying that \(\Gamma(X,\sigma)\) is weakly connected.
Case 2. \(\sigma\) is a circular permutation of length \(n-1\).
Let \(\mathop{\mathrm{fix}}\sigma=\{u_{0}\}\). Fix an arbitrary tree \(X\in\mathop{\mathrm{Tr}}(V)\) and any proper partition \(E(X)=E_{1}\sqcup E_{2}\). Choose an edge \(u_{0}v\in E_{X}(u_{0})\). Without loss of generality, suppose \(u_{0}v\in E_{1}\). Since the partition is proper, \(E_{2}\neq\emptyset\). Consider an arbitrary edge \(xy\in E_{2}\). Let \(x\in[u_{0},y]_{X}\). Since \(\sigma\) is circular of length \(n-1\), it cyclically permutes the set \(V(X)\setminus\{u_{0}\}\). Hence, there exists a number \(m\geq 1\) such that \(\sigma^{m}(v)=y\). Therefore, \(xy\in E_{X}([u_{0},y]_{X})=E_{X}([\sigma^{m}(u_{0}),\sigma^{m}(v)]_{X})\) which means that \(xy\) is reachable from \(u_{0}v\) in \(\Gamma(X,\sigma)\) by Corollary 2.5. Thus, \(\Gamma(X,\sigma)\) is weakly connected by Corollary 2.2.
Case 3. \(\sigma\) is a permutation such that the periods of \(\sigma\)-periodic points with disjoint orbits are pairwise incomparable under division.
Since \(n\geq 2\), we have \(\mathop{\mathrm{fix}}\sigma=\emptyset\). By Theorem 2.7, this implies that there is a \(\sigma\)-negative edge \(uv\in E(X)\). Put \(A_{0}=\{u,v\}\), and consider the map \(f\colon 2^{V(X)}\to 2^{V(X)}\) defined by \[f(A)=\mathop{\mathrm{Conv}}_{X}(A\cup\sigma(A)) \ \text{for}\ A\subset V(X).\]
Since \(|A|\leq|f(A)|\) for all \(A\subset V(X)\), and \(V(X)\) is finite, there exists \(k\geq 0\) with \(f^{k+1}(A_{0})=f^{k}(A_{0})\). A simple induction argument, together with Lemma 3.3, shows that \(f^{k}(A_{0})\) is a good set (recall the definition of a good set before Lemma 3.3), as well as a \(\sigma\)-invariant set.
Thus, if \(f^{k}(A_{0})=V(X)\), then we are done. Otherwise, there exists \(b\in V(X)\setminus f^{k}(A_{0})\) with an edge \(ab\in E(X)\) for some \(a\in f^{k}(A_{0})\). Let \(m\in\mathbb{N}\) be the period of \(a\), and \(l\in\mathbb{N}\) be the period of \(b\). Since \(m\) and \(l\) are incomparable under division, we have \(\sigma^{l}(a)\neq a\) and \(\sigma^{l}(b)=b\) (see Figure 7). Hence, every edge from the metric interval \([\sigma^{l}(a),\sigma^{l}(b)]_{X}=[\sigma^{l}(a),b]_{X}\) is reachable from \(ab\) in \(\Gamma(X,\sigma)\). In particular, this is true for the non-empty set of edges \(E_{X}([\sigma^{l}(a),a]_{X})\) (as \([\sigma^{l}(a),a]_{X}\subset[\sigma^{l}(a),b]_{X}\) by construction of the edge \(ab\)). However, \([\sigma^{l}(a),a]_{X}\subset f^{k}(A_{0})\). Thus, \(ab\) lies in the same weak component in \(\Gamma(X,\sigma)\) as the edges from \(E_{X}(f^{k}(A_{0}))\).
Further, we consider the set \(A_{1}=f^{k}(A_{0})\cup\{b\}\). It is clear that \(A_{1}\) is a good set with a \(\sigma\)-negative edge inside it. Hence, by a similar argument as for the iterations of \(A_{0}\) under \(f\), we can conclude that for some \(k'\geq0\), the set \(f^{k'}(A_{1})\) is also good. Again, if \(f^{k'}(A_{1})=V(X)\), then we are done. Otherwise, we proceed as in the case with \(A_{0}\) to build strictly larger good sets. Since \(X\) is finite, after finite number of steps in this process, we exhaust all the vertices in \(X\), and conclude that \(V(X)\) is a good set, meaning that all the edges from \(E(X)\) lie in a common weak component in \(\Gamma(X,\sigma)\).
◻
We illustrate the necessity of the conditions in Theorem 3.4 with the following two examples.
Example 3.5. (a) Let \(V=\{1,\dots,8\}\) and \(\sigma_{2}\in\mathop{\mathrm{Tr}}(V)\) be the nilpotent map from Example 3.2. Clearly, \(\sigma_{2}\) is not path-nilpotent. Also, \(V\setminus\mathop{\mathrm{Im}}\sigma=\{1,5,6\}\). Consider the function \(f\colon V\setminus\mathop{\mathrm{Im}}\sigma\to\mathbb{N}\) from the proof of Claim 1 in the necessity part of Theorem 3.4. We have \(f(1)=f(6)=2\) and \(f(5)=3\). Now, consider an element \(x_{0}=1\), which minimizes \(f\). Then \(V'=V\setminus\{1,8\}\). Also, put \(y=4\in\sigma^{-1}(2)=\sigma^{-1}(\sigma^{2}(x_{0}))\) and \(z=7\in\sigma^{-1}(4)\cap V'\).
Let \(X'\in\mathop{\mathrm{Tr}}(V)\) be an arbitrary tree on \(V'\), for instance, the star centered at \(2\). Add to \(X'\) two new edges \(zx_{0}=71\) and \(\sigma(z)\sigma(x_{0})=48\) to form a tree \(X\in\mathop{\mathrm{Tr}}(V)\). It is clear that \(\Gamma(X,\sigma)\) is not weakly connected as these two edges induce a weak component in it.
(b) Let \(V=\{1,\dots,9\}\) and \(\sigma=(123)(456789)\in\mathcal{S}(V)\) be a permutation of \(V\) with lengths of cycles \(3\) and \(6\). As these lengths comparable by division, we can use the construction from the proof of Claim 4 in the necessity part of Theorem 3.4 to construct the corresponding tree \(X\). For this, put \(u=1\), \(m=3\), and \(v=4\), \(k=6\). Further, fix any tree \(X'\in\mathop{\mathrm{Tr}}(V\setminus\mathop{\mathrm{orb}}_{\sigma}(v))=\mathop{\mathrm{Tr}}(\{1,2,3\})\), such as the star centered at \(2\). Now add six new edges \(14\), \(17\), \(25\), \(28\), \(36\), \(39\) to \(X'\). Then these six edges induce a weak component in \(\Gamma(X,\sigma)\).
And the next example illustrates the key idea from the proof of the sufficiency of the third condition in Theorem 3.4.
Example 3.6. Consider a tree \(X\) with the vertex set \(V(X)=\{1,\dots,9,x,y\}\) and the edge set \(E(X)=\{12,16,23,24,27,35,38,3x,49,7y\}\) along with its permutation \(\sigma=(12345)(6789)(xy)\). It is clear that \(\sigma\) satisfies the third condition from Theorem 3.4. Further, there is a \(\sigma\)-negative edge \(uv=23\) in \(X\). Put \(A_{0}=\{2,3\}\). Then \(f(A_{0})=\{2,3,4\}\), \(f^{2}(A_{0})=\{2,3,4,5\}\), and \(f^{3}(A_{0})=\{1,2,3,4,5\}\) is a good \(\sigma\)-invariant set (in particular, \(f^{4}(A_{0})=f^{3}(A_{0})\)). Take two adjacent vertices \(a=2\in f^{3}(A_{0})\) and \(b=7\notin f^{3}(A_{0})\). We have that \(a\) has a period of \(5\) and \(b\) has a period of \(4\) under \(\sigma\). Hence, the edge \(ab\) covers the interval \([\sigma^{4}(a),\sigma^{4}(b)]_{X}=[\sigma^{4}(a),b)]_{X}=[1,7]_{X}=\{1,2,7\}\). Thus, the set \(A_{1}=f^{3}(A_{0})\cup\{b\}=\{1,2,3,4,5,7\}\) is also good, and we can similarly consider its iterations under \(f\). Specifically, we have \(f^{2}(A_{1})=A_{1}\cup\{8\}\), \(f^{3}(A_{1})=A_{1}\cup\{8,9\}\), and \(f^{4}(A_{1})=A_{1}\cup\{6,8,9\}\). The last set is good and \(\sigma\)-invariant. Thus, we again take two adjacent vertices \(3\in f^{4}(A_{1})\) and \(x\notin f^{4}(A_{1})\). By considering a good set \(A_{2}=f^{4}(A_{1})\cup\{x\}\), we arrive at the equality \(f(A_{2})=V(X)\). Lemma 3.3 then guarantees that \(f(A_{2})=V(X)\) is a good set as well.
A digraph \(D\) is called an M-graph if there is a tree \(X\) and a map \(\sigma\colon V(X)\to V(X)\) such that \(D\) is isomorphic to \(\Gamma(X,\sigma)\). For graph-theoretic properties of M-graphs, see the papers [12, 11]. For the properties of periodic digraphs (which are Markov graphs for cyclic permutations of paths), we refer to the works [14, 15, 16].
In this section, we address the following broad problem. Given a fixed M-graph \(D\), under what conditions on a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is isomorphic to \(D\)? For example, it is clear that \(\Gamma(X,\sigma)\) is an empty digraph if and only if \(\sigma\) is a constant map.
We start by considering this problem for two simple classes of weakly (in fact, strongly) connected digraphs: complete digraphs and cycles.
Recall that a proper coloring of a graph \(G\) is any map of the form \(f\colon V(G)\to C\) with \(f(u)\neq f(v)\) for all edges \(uv\in E(G)\). The pairs \((X,\sigma)\) that produce complete digraphs \(\Gamma(X,\sigma)\) were characterized in [10].
Proposition 3.7. [10, Proposition 3.13] Let \(X\) be a tree and \(\sigma\colon V(X)\to V(X)\) be a map. Then \(\Gamma(X,\sigma)\) is complete if and only if \(X\) is a path and \(\sigma\) is a proper coloring of \(X\) with \(\mathop{\mathrm{Im}}\sigma=\mathop{\mathrm{Leaf}}(X)\).
By examining the dynamical structure of maps \(\sigma\) in Proposition 3.7, we obtain the answer to the posed problem for complete digraphs \(D\).
Proposition 3.8. Let \(V\) be a set with \(n=|V|\geq 3\). For a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) with the complete Markov graph \(\Gamma(X,\sigma)\) if and only if \(|\mathop{\mathrm{Im}}\sigma|=2\), say \(\mathop{\mathrm{Im}}\sigma=\{u,v\}\), and one of the following conditions hold:
(a) \(\sigma|_{\mathop{\mathrm{Im}}\sigma}\) is constant, say \(\sigma(u)=\sigma(v)=u\), and \(|\sigma^{-1}(u)|=\frac{n+1}{2}\), \(|\sigma^{-1}(v)|=\frac{n-1}{2}\);
(b) \(\sigma(u)=u\), \(\sigma(v)=v\), and \(|\sigma^{-1}(u)|=|\sigma^{-1}(v)|=\frac{n}{2}\);
(c) \(\sigma(u)=v\), \(\sigma(v)=u\), and \(|\sigma^{-1}(u)|=|\sigma^{-1}(v)|=\frac{n}{2}\).
Proof. Necessity. Assume that \(\Gamma(X,\sigma)\) is complete. Proposition 3.7 suggests that \(X\) is a path and \(\sigma\) is a proper coloring of \(X\) with \(\mathop{\mathrm{Im}}\sigma=\mathop{\mathrm{Leaf}}(X)\). Let \(\mathop{\mathrm{Leaf}}(X)=\{u,v\}\).
First, suppose \(n\) is odd. Then \(\sigma(u)=\sigma(v)\). Without loss of generality, assume \(\sigma(u)=\sigma(v)=u\). It is evident that \(\sigma|_{\mathop{\mathrm{Im}}\sigma}\) is constant, and \(|\sigma^{-1}(u)|=\frac{n+1}{2}\), \(|\sigma^{-1}(v)|=\frac{n-1}{2}\).
Similarly, let \(n\) be even. Here we have two different cases. If \(\sigma(u)=u\), then \(\sigma(v)=v\), and \(|\sigma^{-1}(u)|=|\sigma^{-1}(v)|=\frac{n}{2}\). If \(\sigma(u)=v\), then \(\sigma(v)=u\) with the same equalities \(|\sigma^{-1}(u)|=|\sigma^{-1}(v)|=\frac{n}{2}\).
Sufficiency. In each of the three cases, we take \(X\) to be a path on \(V\) with \(\mathop{\mathrm{Leaf}}(X)=\{u,v\}\), and such that no two inner vertices from the same pre-image \(\sigma^{-1}(u)\) or \(\sigma^{-1}(v)\) are being adjacent. We can do this since we have nearly equal sizes of these pre-images in each case. ◻
Before addressing the posed problem for cycles \(D\), we need to introduce a new definition and a supplementary result. A map \(\sigma\colon V(G)\to V(H)\) between two connected graphs if called metric (or non-expanding, or \(1\)-Lipschitz) if \(d_{H}(\sigma(u),\sigma(v))\leq d_{G}(u,v)\) for all \(u,v\in V(G)\). It is fairly easy to prove that \(\sigma\) is metric if and only if \(d_{H}(\sigma(u),\sigma(v))\leq 1\) for all edges \(uv\in E(G)\). Hence, metric maps provide a natural generalization of graph homomorphisms.
Proposition 3.9. [13, Proposition 3.1(1)] Let \(\sigma\colon V(X)\to V(X)\) be a metric map on a tree \(X\). Then \(n(X,\sigma)\leq 1\). In addition, the equality \(n(X,\sigma)=1\) necessarily implies \(p(X,\sigma)=0\).
With these preparations in mind, recalling Proposition 2.6, we can easily characterize maps \(\sigma\) that admit trees \(X\) with \(\Gamma(X,\sigma)\) being a cycle.
Proposition 3.10. Let \(V\) be a set with \(n=|V|\geq 3\). For a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is a cycle if and only if \(\sigma\) is a circular permutation of length \(n-1\).
Proof. Necessity. If \(\Gamma(X,\sigma)\) is a cycle, then \(\sigma\) is an automorphism of \(X\) by Proposition 2.6. In particular, \(\sigma\) is a metric permutation. Hence, by Proposition 3.9, we have \(n(X,\sigma)\leq 1\). If \(uv\in E(X)\) is a \(\sigma\)-negative edge, then \(\sigma(u)=v\) and \(\sigma(v)=u\) as \(\sigma\) is an automorphism. But then \(\Gamma(X,\sigma)\) has a loop at vertex \(uv\), which is a contradiction (as \(n\geq 3\) implies \(|E(X)|\geq 2\)). Thus, \(n(X,\sigma)=0\). Theorem 2.7 then asserts that \(\sigma\) has a fixed point. Let \(u_{0}\in\mathop{\mathrm{fix}}\sigma\). We will prove that \(X\) is a star centered at \(u_{0}\). Indeed, it is clear that the neighborhood \(N_{X}(u_{0})\) is \(\sigma\)-invariant. Consequently, the edge set \(E_{X}(u_{0})\) induce a cycle in \(\Gamma(X,\sigma)\). This is possible only if \(E_{X}(u_{0})=E(X)\), which means that \(\sigma\) is a circular permutation of length \(n-1\).
Sufficiency. Let \(X\) be a star centered at the unique fixed point of \(\sigma\). Then it is evident that \(\Gamma(X,\sigma)\) is a cycle. ◻
Next, we consider several related classes of weakly connected digraphs: paths, in-stars, and out-stars. The following result addresses the posed problem for paths.
Proposition 3.11. Let \(V\) be a set with \(n=|V|\geq 1\). For a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is a path if and only if \(\sigma\) is path-nilpotent.
Proof. Necessity. Since a path \(\Gamma(X,\sigma)\) is weakly connected, Theorem 3.4 suggests that \(\sigma\) is one of the three types. However, \(\Gamma(X,\sigma)\) contains a vertex with zero out-degree, implying that \(\sigma\) is not a permutation. Hence, by Theorem 3.4, \(\sigma\) is a path-nilpotent map.
Sufficiency. Let \(\sigma\) be a path-nilpotent map. Then there is a linear ordering of \(V=\{u_{0},\dots,u_{n-1}\}\) with \(\sigma(u_{i})=u_{i-1}\) for \(1\leq i\leq n-1\), and \(\sigma(u_{0})=u_{0}\). Consider a path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(E(X)=\{u_{i}u_{i-1}:1\leq i\leq n-1\}\). Then it is clear that \(\Gamma(X,\sigma)\) is a path. ◻
Note that trees \(X\), which possess maps \(\sigma\) with Markov graphs \(\Gamma(X,\sigma)\) being paths, have been fully characterized in [13, Theorem 4.2].
We conclude this section by considering two types of digraphs derived from tree orientations. An in-star is a digraph which is obtained from an undirected star \(X\) by giving its edges orientations towards the center of \(X\). Similarly, an out-star is a digraph obtained from an in-star by reversing orientations of its arcs.
Proposition 3.12. Let \(V\) be a set with \(n=|V|\geq 3\). For a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is an in-star if and only if \(|\mathop{\mathrm{Im}}\sigma|=2\) and \(\sigma|_{\mathop{\mathrm{Im}}\sigma}\) is constant.
Proof. Necessity. Let \(\Gamma(X,\sigma)\) be an in-star with an edge \(uv\in E(X)\) having zero out-degree. Then \(\sigma(u)=\sigma(v)\). And since for any other edge \(e\in E(X)\setminus\{uv\}\), it holds \(N_{\Gamma(X,\sigma)}^{+}(e)=\{uv\}\), we have \(\sigma(x)\in\{u,v\}\) for all \(x\in V(G)\setminus\{u,v\}\). In particular, this is true for all vertices \(x\) from \(N_{X}(u)\setminus\{v\}\) and \(N_{X}(v)\setminus\{u\}\). Hence, it also holds for \(u\) and \(v\). Thus, \(|\mathop{\mathrm{Im}}\sigma|=2\) and \(\sigma|_{\mathop{\mathrm{Im}}\sigma}\) is constant.
Sufficiency. Assume \(\mathop{\mathrm{Im}}\sigma=\{u,v\}\) and \(\sigma(u)=\sigma(v)=u\). Fix an element \(x_{0}\in\sigma^{-1}(v)\), and consider a tree \(X\in\mathop{\mathrm{Tr}}(V)\) with \[E(X)=\{uv\}\cup\left\{ux:x\in\sigma^{-1}(v)\right\}\cup\left\{x_{0}y:y\in\sigma^{-1}(u)\setminus\{v\}\right\}.\]
Then the edge \(uv\) has zero out-degree in \(\Gamma(X,\sigma)\). Also, for any edge \(ux\in E(X)\) with \(x\in\sigma^{-1}(v)\), we have \(\sigma(u)=u\), \(\sigma(x)=v\). And for any edge \(x_{0}y\in E(X)\) with \(y\in\sigma^{-1}(u)\setminus\{v\}\), it holds \(\sigma(x_{0})=v\), \(\sigma(y)=u\). Thus, for all edges \(e\in E(X)\setminus\{uv\}\), we have \(N_{\Gamma(X,\sigma)}^{+}(e)=\{uv\}\). Therefore, \(\Gamma(X,\sigma)\) is an in-star. ◻
Proposition 3.13. Let \(V\) be a set with \(n=|V|\geq 3\). For a map \(\sigma\in\mathcal{T}(V)\), there exists a tree \(X\in\mathop{\mathrm{Tr}}(V)\) such that \(\Gamma(X,\sigma)\) is an out-star if and only if \(\sigma\) is non-constant, and there exists \(x\in V\setminus\mathop{\mathrm{Im}}\sigma\) such that \(\sigma|_{V\setminus\{x\}}\) is constant.
Proof. Necessity. Let \(\Gamma(X,\sigma)\) be an out-tree. Then there exists an edge \(xy\in E(X)\) with \(N_{\Gamma(X,\sigma)}^{+}=E_{X}([\sigma(x),\sigma(y)]_{X})=E(X)\setminus\{xy\}\), and any other edge \(e\in E(X)\setminus\{xy\}\) has zero out-degree in \(\Gamma(X,\sigma)\). Thus, \(\sigma\) is constant on the interval \([\sigma(x),\sigma(y)]_{X}\). Withot loss of generality, assume that \(y\in[\sigma(x),\sigma(y)]_{X}\). Then \(x\notin[\sigma(x),\sigma(y)]_{X}\) (as otherwise, \(xy\) would have a loop in \(\Gamma(X,\sigma)\)). In particular, \(\sigma(x)\neq x\). It is also clear that \(x\in V\setminus\mathop{\mathrm{Im}}\sigma\).
Sufficiency. Let \(\sigma(y)=u\) for all \(y\in V\setminus\{x\}\). Clearly, \(u\neq x\) as \(x\in V\setminus\mathop{\mathrm{Im}}\sigma\). Also, \(\sigma(x)\neq x\). Consider any path \(X\in\mathop{\mathrm{Tr}}(V)\) with \(\mathop{\mathrm{Leaf}}(X)=\{x,\sigma(x)\}\) and \(ux\in E(X)\). Then \(N_{\Gamma(X,\sigma)}^{+}(ux)=E_{X}([u,\sigma(x)]_{X})=E(X)\setminus\{ux\}\). Also, other edges \(e\in E(X)\setminus\{ux\}\) have zero out-degrees in \(\Gamma(X,\sigma)\). Thus, the Markov graph \(\Gamma(X,\sigma)\) is an out-star. ◻
In light of Propositions 3.8 and 3.12, we note that the condition in Proposition 3.13 is equivalent to the following: \(|\mathop{\mathrm{Im}}\sigma|=2\), \(\sigma|_{\mathop{\mathrm{Im}}\sigma}\) is constant, say \(\mathop{\mathrm{Im}}\sigma=\{u,v\}\) and \(\sigma(u)=\sigma(v)=u\), and also \(|\sigma^{-1}(v)|=1\).
The author is deeply grateful to the Armed Forces of Ukraine for keeping Kyiv safe during the preparation of this paper. Special thanks go to Kateryna Antoshyna for her invaluable discussions, which significantly improved the clarity of the proof of sufficiency in Theorem 3.4.