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

21 publications found

2025
Journal article

Graphs With Odd And Even Distances Between Non‑Cut Vertices

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko, Kateryna Antoshyna

2024
Journal article

Dynamical Structure Of Metric And Linear Self‑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

2017
Journal article

On The Abstract Properties Of Markov Graphs For Maps On Trees

Publisher: Matematicki Bilten

Authors: Sergiy Kozerenko

2020
Journal article

Periods In XOR Parallel Dynamical Systems Over Directed Dependency Graphs

Publisher: Applied Mathematics and Computation

Authors: Sergiy Kozerenko, Jose C. Valverde