Journal article

An Optimal Lower Bound For The Size Of Periodic Digraphs

Year:

2023

Published in:

Discrete Mathematics Letters
trees
permutations
Markov graphs
strongly connected digraphs

Markov graphs form a special class of digraphs constructed from self-maps on the vertex sets of combinatorial trees. In this paper, the trees that admit cyclic permutations of their vertex sets with non-strongly connected Markov graphs in terms of the existence of a special subset of edges are characterized. Additionally, the structure of self-maps of finite sets, which produce strongly connected Markov graphs for all trees, is described. A similar question, concerning which self-maps produce strongly connected Markov graphs for some trees, is answered for the class of permutations.

Other publications by

16 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

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