Journal article

Discrete Markov graphs: loops, fixed points and maps preordering

Year:

2016

Published in:

Society for the Promotion of Science
Markov graphs
one-dimensional dynamics
maps on trees
Second Neighbourhood Conjecture
Caccetta-H¨aggkvist Conjecture

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.

Other publications by

24 publications found

2025
Journal article

On Strongly Connected Markov Graphs Of Maps On Combinatorial Trees

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko

2023
Journal article

Unique Eccentric Point Graphs And Their Eccentric Digraphs

Publisher: Discrete Mathematics

Authors: Sergiy Kozerenko, Artem Hak, Vladyslav Haponenko, Andrii Serdiuk

2024
Journal article

All‑Path Convexity: Two Characterizations, General Position Number, And One Algorithm

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko, Vladyslav Haponenko

2016
Journal article

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

Publisher: Romanian Journal of Mathematics and Computer Science

Authors: Sergiy Kozerenko

2018
Journal article

On Expansive And Anti‑Expansive Tree Maps

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko