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

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

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

2024
Journal article

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

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko, Vladyslav Haponenko

2025
Conference proceedings

Полідерева зі слабко зв’язними реберними орграфами

Publisher: КПІ ім. Ігоря Сікорського

Authors: Sergiy Kozerenko, Bohdan-Yarema Dekhtiar

2025
Conference proceedings

Unique eccentric point graphs of diameter at most four

Publisher: XV Ukraine Algebra Conference

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

2020
Journal article

Periods In XOR Parallel Dynamical Systems Over Directed Dependency Graphs

Publisher: Applied Mathematics and Computation

Authors: Sergiy Kozerenko, Jose C. Valverde

2017
Journal article

On The Abstract Properties Of Markov Graphs For Maps On Trees

Publisher: Matematicki Bilten

Authors: Sergiy Kozerenko

2021
Journal article

More On Linear And Metric Tree Maps

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko