On disjoint union of M-graphs
Given a pair (X,σ) consisting of a finite tree X and its vertex self-map σ one can construct the corresponding Markov graph Γ(X,σ) which is a digraph that encodes σ-covering relation between edges in X. M-graphs are Markov graphs up to isomorphism. We obtain several sufficient conditions for the dis...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2017 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2017
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/156635 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On disjoint union of M-graphs / S. Kozerenko // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 262-273. — Бібліогр.: 10 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-156635 |
|---|---|
| record_format |
dspace |
| spelling |
Kozerenko, S. 2019-06-18T18:10:42Z 2019-06-18T18:10:42Z 2017 On disjoint union of M-graphs / S. Kozerenko // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 262-273. — Бібліогр.: 10 назв. — англ. 1726-3255 2010 MSC:05C20, 37E25, 37E15. https://nasplib.isofts.kiev.ua/handle/123456789/156635 Given a pair (X,σ) consisting of a finite tree X and its vertex self-map σ one can construct the corresponding Markov graph Γ(X,σ) which is a digraph that encodes σ-covering relation between edges in X. M-graphs are Markov graphs up to isomorphism. We obtain several sufficient conditions for the disjoint union of M-graphs to be an M-graph and prove that each weak component of M-graph is an M-graph itself. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On disjoint union of M-graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On disjoint union of M-graphs |
| spellingShingle |
On disjoint union of M-graphs Kozerenko, S. |
| title_short |
On disjoint union of M-graphs |
| title_full |
On disjoint union of M-graphs |
| title_fullStr |
On disjoint union of M-graphs |
| title_full_unstemmed |
On disjoint union of M-graphs |
| title_sort |
on disjoint union of m-graphs |
| author |
Kozerenko, S. |
| author_facet |
Kozerenko, S. |
| publishDate |
2017 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
Given a pair (X,σ) consisting of a finite tree X and its vertex self-map σ one can construct the corresponding Markov graph Γ(X,σ) which is a digraph that encodes σ-covering relation between edges in X. M-graphs are Markov graphs up to isomorphism. We obtain several sufficient conditions for the disjoint union of M-graphs to be an M-graph and prove that each weak component of M-graph is an M-graph itself.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/156635 |
| citation_txt |
On disjoint union of M-graphs / S. Kozerenko // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 262-273. — Бібліогр.: 10 назв. — англ. |
| work_keys_str_mv |
AT kozerenkos ondisjointunionofmgraphs |
| first_indexed |
2025-11-24T06:35:33Z |
| last_indexed |
2025-11-24T06:35:33Z |
| _version_ |
1850843125263630336 |
| fulltext |
“adm-n4” 22:47 page #84
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 24 (2017). Number 2, pp. 262–273
© Journal “Algebra and Discrete Mathematics”
On disjoint union of M-graphs
Sergiy Kozerenko
Communicated by V. V. Kirichenko
Abstract. Given a pair (X, σ) consisting of a finite tree
X and its vertex self-map σ one can construct the corresponding
Markov graph Γ(X, σ) which is a digraph that encodes σ-covering
relation between edges in X. M-graphs are Markov graphs up to
isomorphism. We obtain several sufficient conditions for the disjoint
union of M-graphs to be an M-graph and prove that each weak
component of M-graph is an M-graph itself.
Introduction
In 1964 Sharkovsky proved the following remarkable theorem.
Theorem 1. [9] If the continuous map f : [0, 1] → [0, 1] has a periodic
point of period n ∈ N, then it also has a periodic point of period m ∈ N
for all m ⊳ n, where
1⊳2⊳22
⊳· · ·⊳2n
⊳· · ·⊳7·2n
⊳5·2n
⊳3·2n
⊳· · ·⊳7·2⊳5·2⊳3·2⊳· · ·⊳7⊳5⊳3
is Sharkovsky’s ordering of N. Moreover, for every number m ∈ N there
exists a continuous map that has a periodic point of period m but does
not have periodic points of periods n ∈ N, where m ⊳ n.
In [10] Straffin proposed a strategy on how to prove Sharkovsky’s the-
orem using some elegant combinatorial arguments. The cornerstone of his
idea is to use directed graphs which naturally arise from orbits of periodic
2010 MSC: 05C20, 37E25, 37E15.
Key words and phrases: tree maps, Markov graphs, Sharkovsky’s theorem.
“adm-n4” 22:47 page #85
S. Kozerenko 263
points. Namely, let x ∈ [0, 1] be n-periodic point of a continuous map
f : [0, 1] → [0, 1]. Consider the orbit orbf (x) = {x, f(x), . . . , fn−1(x)} =
{x1 < · · · < xn} and its natural ordering inherited from the interval.
Periodic graph Gf (x) has the vertex set {1, . . . , n − 1} and the arc set
{(i, j) : min{f(xi), f(xi+1)} 6 xj < max{f(xi), f(xi+1)}}. Here each
1 6 i 6 n − 1 represents the minimal interval [xi, xi+1] and there is an arc
i → j in Gf (x) if [xi, xi+1] “covers” [xj , xj+1] under f . Periodic graphs are
useful in combinatorial dynamics because of the following result known
as Itinerary lemma.
Lemma 1. [10] Let x ∈ [0, 1] be some periodic point of a continuous
map f : [0, 1] → [0, 1]. Suppose that there is a closed walk W = {i0 →
· · · → im−1 → i0} of length m in Gf (x). Then there exists a periodic
point y ∈ [0, 1] such that fm(y) = y and fk(y) ∈ [xik
, xik+1] for all
0 6 k 6 m − 1. Moreover, if W is primitive, then the period of y equals
m.
Here the closed walk is called primitive if it is not entirely consists
of a smaller walk traced several times. Note that Lemma 1 admits a
converse statement. Namely, for any periodic point x ∈ [0, 1] of f we
can consider its linearization Lx(f) : [0, 1] → [0, 1] which is a “connect-
the-dots” map with respect to the orbit orbf (x). Then each m-periodic
point of Lx(f) corresponds to some primitive closed walk of length m in
GLx(f)(x) = Gf (x).
Full proof of Sharkovsky’s theorem using periodic graphs can be found
in [2]. Graph-theoretic properties of periodic graphs were studied in [6–8].
These are include calculation of the number of non-isomorphic periodic
graphs with given number of vertices [6] and obtaining graph-theoretic
criteria for periodic graphs [7] and their induced subgraphs [8].
Similar approach can be used for dynamics of continuous maps on
finite topological trees (see [1] for the Sharkovsky-type result in this case).
The corresponding digraphs are called Markov graphs. These are can be
defined for combinatorial trees and their vertex maps. Thus, periodic
graphs appear as a particular case of Markov graphs where underlying
trees are paths and maps are cyclic permutations. M-graphs then defined
as Markov graphs up to isomorphism.
In [3] maps on trees were characterized for several classes of M-graphs
including complete digraphs, complete bipartite digraphs, disjoint unions
of cycles and digraphs in which each arc is a loop. It is also shown [4] that
M-graphs satisfy Seymour’s Second Neighbourhood Conjecture as well
as Caccetta–Häggkvist Conjecture. Various transformations including
“adm-n4” 22:47 page #86
264 On disjoint union of M-graphs
deletion and addition of vertices, doubling and reverse doubling of vertices
and taking disjoint unions of M-graphs are studied in [5]. Also, it is proved
that there exist exactly 11 pairwise non-isomorphic M-graphs which are
tournaments as well as 86 pairwise non-isomorphic 3-vertex M-graphs
(again, see [5]).
In this paper we obtain several sufficient conditions for the disjoint
union of M-graphs to be an M-graph and prove that each weak component
of M-graph is an M-graph itself.
1. Definitions and preliminary results
In what follows map is just a function. For any given map σ by Im σ
and fix σ we denote its image and the set of its fixed points, respectively.
A graph G is a pair (V, E), where V = V (G) is the set of its vertices
and E = E(G) the set of its edges. By EG(u) we denote the set of
all edges incident to the vertex u in G. A vertex u is called isolated if
|EG(u)| = 0. Similarly, u is a leaf vertex provided |EG(u)| = 1. The
unique edge incident to a leaf vertex is called a leaf edge. The set of all leaf
vertices in G is denoted by L(G). For the set of vertices A ⊂ V (G) we put
E(A) = {uv ∈ E(G) : u, v ∈ A} and ∂GA = {u ∈ A : EG(u)−E(A) 6= ∅}.
By G[A] and G[E′] we denote the subgraphs of G induced by A ⊂ V (G)
and E′ ⊂ E(G), respectively.
A graph G is called connected if for every pair of its vertices u, v ∈ V (G)
there exists a path joining them. The minimum number of edges in such
a path is called the distance dG(u, v) between u and v in G. The set of
vertices A ⊂ V (G) is connected if the induced subgraph G[A] is connected.
Similarly, E′ ⊂ E(G) is connected if so is G[E′].
The eccentricity of a vertex u in a connected graph G is the value
eccG(u) = maxv∈V (G) dG(u, v). For the pair of vertices u, v ∈ V (G) in a
connected graph G we put [u, v]G = {w ∈ V (G) : dG(u, w) + dG(w, v) =
dG(u, v)}. The set A ⊂ V (G) is convex provided [u, v]G ⊂ A for all
u, v ∈ A. The convex hull ConvG(A) of A is defined as the smallest
convex set containing A.
Put dG(u, A) = minv∈A dG(u, v) and dG(A, B) = minu∈B dG(u, A)
for all vertex sets {u}, A, B ⊂ V (G) in a connected graph G. The set
A ⊂ V (G) is called Chebyshev if for every vertex u ∈ V (G) there exists
a unique v ∈ A with dG(u, v) = dG(u, A). The corresponding map prA :
V (G) → V (G), where prA(u) = v is called the projection on a Chebyshev
set A.
“adm-n4” 22:47 page #87
S. Kozerenko 265
A tree is a connected acyclic graph. It should be noted that in a tree
each connected set of vertices is Chebyshev.
A directed graph or digraph Γ is a pair (V, A), where V = V (Γ) is the set
of its vertices and A = A(Γ) ⊂ V ×V is the set of its arcs. If (u, v) ∈ A(Γ),
then we write u → v in Γ. The arc of the form u → u is called a loop.
For the vertex u ∈ V (Γ) we put N+
Γ (u) = {v ∈ V (Γ) : u → v in Γ} and
N−
Γ (u) = {v ∈ V (Γ) : v → u in Γ}. The cardinalities d+
Γ (u) = |N+
Γ (u)|
and d−
Γ (u) = |N−
Γ (u)| are called the outdegree and the indegree of u,
respectively.
A digraph Γ is called complete provided A(Γ) = V (Γ)×V (Γ). Similarly,
Γ is empty if A(Γ) = ∅. By Kn and Kn we denote the complete and the
empty digraph with n vertices, respectively.
A digraph is called weakly connected if its underlying graph (which is
obtained by “forgetting” orientation of the edges and ignoring loops) is
connected. Weak component of a digraph is its maximal weakly connected
subgraph. By Γ1 ⊔ Γ2 we denote the disjoint union of digraphs Γ1 and Γ2.
A pair (X, u0) consisting of a tree X and its distinguished vertex
u0 ∈ V (X) is called a rooted tree. The digraph Γ which is obtained from
the rooted tree (X, u0) by orienting the edges of X towards u0 is called
an in-tree. The vertex u0 is the center of an in-tree Γ. It is easy to see
that for an in-tree its center is the unique vertex with zero outdegree.
For every map f : X → X one can define its functional graph as a
digraph with the vertex set X and the arc set {(x, y) : f(x) = y}. A
digraph is called functional if it isomorphic to a functional graph for some
map. It is easy to see that Γ is functional digraph if and only if d+
Γ (v) = 1
for all v ∈ V (Γ). Similarly, Γ is called partial functional if d+
Γ (v) 6 1
for all v ∈ V (Γ). Each partial functional digraph Γ corresponds to some
partial map of the form f : V (Γ) → V (Γ).
Definition 1. Let X be a tree and σ : V (X) → V (X) be some map. The
Markov graph Γ = Γ(X, σ) has the vertex set V (Γ) = E(X) and there is an
arc e1 → e2 in Γ if u2, v2 ∈ [σ(u1), σ(v1)]X for ei = uivi ∈ V (Γ), i = 1, 2.
In other words, N+
Γ (uv) = E([σ(u), σ(v)]X) for all edges uv ∈ E(X).
Example 1. Consider the tree X with V (X) = {1, . . . , 7}, E(X) =
{12, 23, 34, 45, 26, 37} and its map σ =
(
1 2 3 4 5 6 7
4 1 3 6 2 4 2
)
which
are shown in Figure 1. Then the corresponding Markov graph Γ(X, σ) is
shown in Figure 2.
“adm-n4” 22:47 page #88
266 On disjoint union of M-graphs
1 2 3 4 5
6 7
Figure 1. The pair (X, σ) from Example 1 (dashed arrows denote σ).
34 26 45
12 23 37
Figure 2. Markov graph Γ(X, σ) for the pair (X, σ) from Example 1.
A digraph Γ is called an M-graph if there exists a pair (X, σ) such
that Γ ≃ Γ(X, σ). Each such a pair is called the realization of Γ.
Lemma 2. [3] Let X be a tree and σ : V (X) → V (X) be a map. Then for
every pair of vertices u, v ∈ V (X) and an edge xy ∈ E([σ(u), σ(v)]X) there
exists an edge wz ∈ E([u, v]X) with wz → xy in Γ(X, σ). In particular,
[σ(u), σ(v)]X ⊂
⋃
wz∈E([u,v]X)
[σ(w), σ(z)]X .
Lemma 3. [5] Let X be a tree, A ⊂ V (X) be some connected set
of vertices, σ : V (X) → V (X) be a map and Γ = Γ(X, σ). Then
Γ(X[A], prA ◦σ) = Γ[E(A)].
Proposition 1. Let X be a tree and σ : V (X) → V (X) be some map.
Put E(σ) = {e ∈ E(X) : d−
Γ (e) > 1}. Then E(σ) = E(ConvX(Im σ)). In
particular, X[E(σ)] is the connected subgraph of X.
Proof. Let V1 = V (E(σ)) and V2 = ConvX(Im σ). If u ∈ V1, then there
exists an edge e = uv ∈ E(σ). By definition, d−
Γ (e) > 1. This means
“adm-n4” 22:47 page #89
S. Kozerenko 267
that there is an edge e′ = u′v′ ∈ E(X) with e′ → e in Γ(X, σ), i.e.
u, v ∈ [σ(u′), σ(v′)]X . Therefore, u ∈ V2.
Conversely, suppose u ∈ V2. Then there exists a pair of vertices x, y ∈
V (X) such that u ∈ [σ(x), σ(y)]X . At first, suppose that σ(x) 6= σ(y).
Then we can fix an edge e = uv ∈ E([σ(x), σ(y)]X). From Lemma 2
it follows that there is an edge e′ ∈ E([x, y]X) with e′ → e in Γ. Thus
d−
Γ (e) > 1 and u ∈ V1. Otherwise, let σ(x) = σ(y). Then u ∈ Im σ. If σ is
a constant map, then E(σ) = E(ConvX(Im σ)) = ∅. Thus, suppose that
σ is non-constant. This means that there exists a vertex v ∈ Im σ − {u}.
Let σ(z) = v. Since u 6= v, we can fix an edge e = uw ∈ E([u, v]X). Again,
by Lemma 2, d−
Γ (e) > 1 which implies u ∈ V1.
2. Main results
From Lemma 3 it strictly follows that each nontrivial M-graph Γ
contains a vertex v ∈ V (Γ) such that Γ − {v} is also an M-graph. In [5]
it was proved that any digraph obtained from an M-graph by deletion
of a vertex with zero outdegree (in particular, an isolated vertex) is an
M-graph itself. We generalize this result using the following theorem.
Theorem 2. Let X be a tree and σ : V (X) → V (X) be some map.
Suppose that we have a collection Ai ⊂ V (X), 1 6 i 6 m of pairwise
disjoint connected sets such that for every 1 6 i 6 m either |σ(∂XAi)| = 1
or there exists 1 6 j 6 m with σ(∂XAi) ⊂ Aj. Then Γ(X, σ)−
⋃m
i=1 E(Ai)
is an M-graph.
Proof. Consider the set of indices I1 = {1 6 i 6 m : |σ(∂XAi)| = 1} and
the corresponding map g : I1 → V (X), where σ(∂XAi) = {g(i)} for all
i ∈ I1. Similarly, the set of indices I2 = {1, . . . , m} − I1 defines the map
f : I2 → {1, . . . , m}, where σ(∂XAi) ⊂ Af(i) for all i ∈ I2.
Take a graph X −
⋃m
i=1 Ai and add to it m new vertices zi for each
1 6 i 6 m with new edges ziyi for all yi ∈ ∂X(V (X) − Ai) to obtain a
new graph X ′. It is easy to see that X ′ is a tree (one can think of X ′ as of
tree which is obtained from X by “contracting” sets Ai into points). Put
σ′(x) =
zi if σ(x) ∈ Ai,
g(i) if x = zi and i ∈ I1,
zf(i) if x = zi and i ∈ I2,
σ(x) otherwise,
for all x ∈ V (X ′). Then Γ(X, σ) −
⋃m
i=1 E(Ai) ≃ Γ(X ′, σ′).
“adm-n4” 22:47 page #90
268 On disjoint union of M-graphs
Corollary 1. Let Γ be an M-graph and v ∈ V (Γ) be its vertex with
N+
Γ (v) ⊂ {v}. Then Γ − {v} is an M-graph. Moreover, if N+
Γ (v) = {v},
then there exists a realization (X, σ) of Γ − {v} such that fix σ 6= ∅.
Proof. Fix some realization (X, σ) of Γ. Let the edge e = ux ∈ E(X)
corresponds to the vertex v ∈ V (Γ). If N+
Γ (v) = ∅, then σ(u) = σ(x). In
this case for the connected set of vertices A = {u, x} we have |σ(∂XA)| = 1.
By Theorem 2, Γ − {v} is an M-graph.
Otherwise, let N+
Γ (v) = {v}. Then σ(u) = u and σ(x) = x, or σ(u) = x
and σ(x) = u. In both cases σ(∂XA) ⊂ A. Again, by Theorem 2, Γ − {v}
is an M-graph. Moreover, with the notation of Theorem 2, σ′(z1) = z1
(here A = A1). Therefore, in this case fix σ′ 6= ∅.
Example 2. Consider the tree X with V (X) = {1, . . . , 7}, E(X) =
{12, 23, 34, 16, 25, 67} and its map σ =
(
1 2 3 4 5 6 7
4 1 5 4 5 2 3
)
. Then
d−
Γ(X,σ)(16) = 0, however Γ(X, σ) − {16} is not an M-graph (see Figure 3).
16 34 12
67 23 25
Figure 3. Markov graph Γ(X, σ) for which Γ(X, σ) − {16} is not an M-graph.
Denote by V0(Γ) = {v ∈ V (Γ) : d−
Γ (v) = 0} the set of vertices with
zero indegree in Γ.
Proposition 2. For every M-graph Γ and 0 6 k 6 |V0(Γ)| there exists
V ′ ⊂ V0(Γ) with |V ′| = k such that Γ − V ′ is an M-graph. In particular,
Γ − V0(Γ) is an M-graph.
Proof. Fix a realization (X, σ) of Γ. Let the edge set E′ ⊂ E(X) cor-
responds to V0(Γ). By Proposition 1, the set E(X) − E′ = E(σ) is
connected. Since X is a connected graph, for any 0 6 k 6 |V0(Γ)| there
exists a connected set of edges E′′ ⊂ E(X) with E(X) − E′ ⊂ E′′
“adm-n4” 22:47 page #91
S. Kozerenko 269
and |E′| = |E(X)| − k. Let V ′ ⊂ V (Γ) corresponds to E(X) − E′′.
Then |V ′| = k and by Lemma 3, Γ − V ′ ≃ Γ(X, σ) − (E(X) − E′′) =
Γ(X, σ)[E′′] = Γ(X[E′′], prV (E′′) ◦σ) is an M-graph.
Note that any digraph obtained from an M-graph by addition of an
isolated vertex is also an M-graph. Using this fact one can conclude that
Γ is an M-graph if and only if so is Γ ⊔ K1. However, not every disjoint
union of two M-graphs is an M-graph itself.
Example 3. Suppose that Γ is obtained from the complete digraph with
two vertices K2 by deletion of a loop. Then Γ is an M-graph, but Γ ⊔ K1
is not (see Figure 4).
Figure 4. Disjoint union of two M-graphs which is not an M-graph.
Remark 1. [5] If we have a pair of trees Xi, i = 1, 2 and a pair of their
maps σi : V (Xi) → V (Xi) with fix σi 6= ∅, i = 1, 2, then the disjoint
union Γ(X1, σ1) ⊔ Γ(X2, σ2) is an M-graph. Indeed, “gluing” realizations
(X1, σ1) and (X2, σ2) together along some pair of fixed vertices we obtain
the realization of Γ(X1, σ1) ⊔ Γ(X2, σ2).
As a corollary of the construction in Remark 1 one can obtain a
sufficient condition for the disjoint union of two M-graphs to be an M-
graph.
Corollary 2. [5] Let Γ1 and Γ2 be a pair of M-graphs with even numbers
of loops in each. Then Γ1 ⊔ Γ2 is an M-graph. In particular, any disjoint
union of two M-graphs without loops is an M-graph itself.
It turns out that for any given M-graph we can provide a graph-
theoretic criterion for the existence of its realization (X, σ) with fix σ 6= ∅.
Proposition 3. Let Γ be a digraph. Then Γ⊔K1 is an M-graph if and only
if Γ is an M-graph and there exists its realization (X, σ) with fix σ 6= ∅.
Proof. Sufficiency of this condition follows from Remark 1, since for K1
there obviously exists its realization (X, σ) with fix σ 6= ∅. Thus, we
must prove only the necessity of this condition. To do so fix a realization
(X ′, σ′) of Γ ⊔ K1. Let the vertex v ∈ V (Γ ⊔ K1) corresponds to a unique
vertex from K1. Then N+
Γ⊔K1
(v) = {v} implying that by Corollary 1, Γ
is an M-graph and there exists its realization (X, σ) with fix σ 6= ∅.
“adm-n4” 22:47 page #92
270 On disjoint union of M-graphs
Corollary 3. If Γ ⊔ K1 is an M-graph, then there exists its realization
(X, σ) with fix σ 6= ∅.
Combining Remark 1 and Proposition 3, we obtain the following
result.
Proposition 4. If for a pair of digraphs Γ1 and Γ2 the digraphs Γ1 ⊔ K1
and Γ2 ⊔ K1 are M-graphs, then Γ1 ⊔ Γ2 is an M-graph.
Theorem 3. Let Γ1 be an M -graph and Γ2 be acyclic partial functional
digraph. Then Γ1 ⊔ Γ2 is also an M -graph.
Proof. Without loss of generality, we can assume that Γ2 is weakly con-
nected. Since Γ2 is acyclic and partially functional, Γ2 is an in-tree. Let
x0 ∈ V (Γ2) be its center (thus, d+
Γ2
(x0) = 0). Denote by X ′ the under-
lying tree of Γ2. For every 0 6 i 6 eccX′(x0) put ai = |N i
X′(x0)| for the
cardinality of the sphere with radius i centered at x0 in X ′.
Now fix a realization (X, σ0) of Γ1. Since V (X) is finite, σ0 has a
periodic point u0 ∈ V (X) with period m > 1. Consider the restriction
σ = σ0|orbσ0
(u0) of σ0 to orbσ0
(u0). Clearly, σ is a cyclic permutation of
orbσ0
(u0).
For every 0 6 i 6 eccX′(x0) add ai new vertices yi
1, . . . yi
ai
to X with
the new edges yi
jσ−i mod m(u0) for all 1 6 j 6 ai (of course, σ0(u0) = u0).
Denote the obtained tree as X ′′. For all u ∈ V (X ′′) put
σ′(u) =
σ(u) if u ∈ V (X),
yi−1
k if u = yi
j , i > 1 and N+
Γ2
(xi
j) = {xi−1
k },
σ(u0) if u = y0
1,
where N i
X′(x0) = {xi
j : 1 6 j 6 ai} (for example, N0
X′(x0) = {x0
1} = {x0}).
Then Γ(X ′′, σ′) ≃ Γ1 ⊔ Γ2 (the edges from E(X) correspond to the
vertices of Γ1 and edges of the form yi
jσ−i mod m(u0) correspond to the
vertices xi
j).
Note that the acyclicity condition in Theorem 3 is essential as can be
seen from the digraph in Example 3.
Example 4. Consider the pair (X, σ) from Example 1 and the corre-
sponding Markov graph Γ1 = Γ(X, σ). Also, let Γ2 be the in-tree depicted
in Figure 5 (the vertices of Γ2 are labeled according to the notation in
the proof of Theorem 3). Thus, x0 is the center of Γ2, eccX′(x0) = 2,
N1
X′(x0) = {x1
1, x1
2}, N2
X′(x0) = {x2
1, x2
2} and a1 = a2 = 2. Put u0 = 4.
“adm-n4” 22:47 page #93
S. Kozerenko 271
Then orbσ(u0) = {4, 6} and therefore m = 2. The corresponding tree X ′′
is shown in Figure 6. We also have σ′(y0
1) = 6, σ′(y1
1) = σ′(y1
2) = y0
1 and
σ′(y2
1) = σ′(y2
2) = y1
2.
x2
1 x1
2
x0 x1
1
x2
2
Figure 5. The in-tree Γ2.
1 2 3 4 5
6 7
y1
1 y1
2
y0
1
y2
1
y2
2
Figure 6. The tree X ′′ from Example 4.
Theorem 4. The disjoint union of any collection of weak components
(in particular, each weak component) in an M-graph is an M-graph itself.
Proof. It is sufficient to prove that for any M-graph Γ and its weak
component Γ′ the digraph Γ − V (Γ′) is an M-graph. To do so fix a
realization (X, σ) of Γ. Let the set of edges E′ ⊂ E(X) corresponds to
the vertex set of Γ′. Consider the components X1, . . . , Xm of the induced
subgraph X[E′] in X and put Ai = V (Xi) for all 1 6 i 6 m.
Suppose that for some 1 6 i 6 m there exists a vertex x ∈ Ai with
σ(x) /∈ ∪m
j=1Aj = V (X[E′]). Then EX(σ(x)) ∩ E′ = ∅. If for some y ∈ Ai
we have σ(x) 6= σ(y), then dX(σ(x), σ(y)) > 2. This means that there is a
vertex u ∈ [σ(x), σ(y)]X such that e = uσ(x) ∈ E(X). By Lemma 2, there
exists an edge e′ ∈ E([x, y]X) ⊂ E(Ai) with e′ → e in Γ(X, σ). Since
“adm-n4” 22:47 page #94
272 On disjoint union of M-graphs
e /∈ E′, Γ′ is not a weak component of Γ. The obtained contradiction
implies that in this case we have σ(x) = σ(y) for every y ∈ Ai. In other
words, |σ(Ai)| = 1.
Now let 1 6 i 6 m is fixed and for every vertex x ∈ Ai there exists
1 6 jx 6 m with σ(x) ∈ Ajx . We want to prove that in this case jx = jy
for each pair of vertices x, y ∈ Ai. To the contrary, suppose jx 6= jy for
some x, y ∈ Ai. Then dX(Ajx , Ajy ) > 1. This implies the existence of an
edge e ∈ E([σ(x), σ(y)]X) − ∪m
k=1E(Ak). Again, from Lemma 2 it follows
that there exists e′ ∈ E([x, y]X) ⊂ E(Ai) with e′ → e in Γ(X, σ) which
is a contradiction. Thus, in this case σ(Ai) ⊂ Aj for some 1 6 j 6 m.
Theorem 2 now asserts that Γ − V (Γ′) is an M-graph.
Corollary 4. If for a pair of digraphs Γ1 and Γ2 their disjoint union
Γ1 ⊔ Γ2 is an M-graph, then both Γ1 and Γ2 are M-graphs.
Proof. Clearly, Γ1 and Γ2 are both disjoint unions of weak components
in Γ1 ⊔ Γ2.
Proposition 5. Let Γ1 and Γ2 be a pair of nontrivial digraphs having
loops at each of their vertices. Then Γ1 ⊔ Γ2 is an M-graph if and only if
Γ1 ⊔ K1 and Γ2 ⊔ K1 are both M-graphs.
Proof. The sufficiency of this condition strictly follows from Proposition 4.
To prove its necessity fix a realization (X, σ) of Γ = Γ1 ⊔ Γ2. Let Γ′ be a
weak component in Γ and E′ ⊂ E(X) be the corresponding set of edges
in X. We want to prove that E′ is connected. To the contrary, suppose
that there is a partition E′ = E1 ⊔ E2 with dX(V (E1), V (E2)) > 1.
Since Γ′ is weakly connected, there is a pair of edges ei = uivi ∈ Ei, i =
1, 2 with e1 → e2 or e2 → e1 in Γ′. Without loss of generality, assume
e1 → e2 in Γ′. We have e1, e2 ∈ N+
Γ(X,σ)(e1) which implies [u1, u2]X ⊂
[σ(u1), σ(v1)]X . However, the inequality dX(V (E1), V (E2)) > 1 asserts
E([u1, u2]X) − E′ 6= ∅. In other words, there exists an edge e′ /∈ E′ such
that e1 → e′ in Γ. Therefore, Γ′ is not a weak component in Γ. The
obtained contradiction proves that E′ is connected.
By Lemma 3, Γ′ ≃ Γ(X, σ)[E′] = Γ(X[E′], prV (E′) ◦σ). Furthermore,
since Γ1 and Γ2 are nontrivial digraphs, we have Γ 6= Γ′. This implies
∂XV (E′) 6= ∅. Fix a vertex w ∈ ∂XV (E′) and an edge e ∈ EX(w) − E′.
Let E′′ be the vertex set of the weak component in Γ(X, σ) which con-
tains e. Similarly, we can prove that E′′ is connected. Also, note that
w ∈ ∂XV (E′′). Finally, the proof of Theorem 4 implies that σ(∂XV (E′)) ⊂
“adm-n4” 22:47 page #95
S. Kozerenko 273
∂XV (E′) as well as σ(∂XV (E′′)) ⊂ ∂XV (E′′). Hence, we can conclude
that σ(w) = w.
Thus, for every weak component Γ′ of Γ there exists its realization
(X ′, σ′) with fix σ′ 6= ∅. But Γ1 (as well as Γ2) is a disjoint union of weak
components in Γ. Combining this fact with Remark 1 and Proposition 4,
we obtain that Γ1 ⊔ K1 as well as Γ2 ⊔ K1 are M-graphs.
Example 5. Consider the path X ≃ P4 with V (X) = {1, 2, 3, 4}, E(X) =
{12, 23, 34} and its vertex map σ =
(
1 2 3 4
3 1 4 2
)
. Then Γ(X, σ) has
a loop at each vertex, but Γ(X, σ) ⊔ K1 is not an M-graph.
References
[1] C. Bernhardt, Vertex maps for trees: algebra and periods of periodic orbits, Discrete
Contin. Dyn. Syst. 14 (2006), 399–408.
[2] C-W. Ho and C. Morris, A graph-theoretic proof of Sharkovsky’s theorem on the
periodic points of continuous functions, Pacific J. Math. 96 (1981), 361–370.
[3] S. Kozerenko, Markov graphs of one-dimensional dynamical systems and their
discrete analogues, Rom. J. Math. Comput. Sci. 6 (2016), 16–24.
[4] S. Kozerenko, Discrete Markov graphs: loops, fixed points and maps preordering, J.
Adv. Math. Stud. 9 (2016), 99–109.
[5] S. Kozerenko, On the abstract properties of Markov graphs for maps on trees, Mat.
Bilten 41 (2017), 5–21.
[6] V. A. Pavlenko, Number of digraphs of periodic points of a continuous mapping of
an interval into itself, Ukrainian Math. J. 39 (1987), 481–486 (in russian).
[7] V. A. Pavlenko, Periodic digraphs and their properties, Ukrainian Math. J. 40
(1988), 455–458 (in russian).
[8] V. A. Pavlenko, On characterization of periodic digraphs, Cybernet. Systems Anal.
25 (1989), 49–54 (in russian).
[9] A. N. Sharkovsky, Coexistence of the cycles of a continuous mapping of the line
into itself, Ukrainian Math. J. 16 (1964), 61–71 (in russian).
[10] P. D. Straffin, Periodic points of continuous functions, Math. Mag. 51 (1978),
99–105.
Contact information
S. Kozerenko Faculty of Mechanics and Mathematics, Taras
Shevchenko National University of Kyiv,
Volodymyrska str., 64, 01033 Kyiv, Ukraine
E-Mail(s): kozerenkosergiy@ukr.net
Received by the editors: 12.03.2017
and in final form 02.11.2017.
|