No Detail Found!

On strongly connected Markov graphs of maps on combinatorial trees

Author(s)
Sergiy Kozerenko National University of Kyiv-Mohyla Academy, Skovorody str. 2, 04070 Kyiv, Ukraine; Kyiv School of Economics, Mykoly Shpaka str. 3, 03113 Kyiv, Ukraine
Abstract
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.
Publication Details
Page(s) 31-38
Published Journal: Discrete Mathematics Letters, Volume: 15, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
permutations, trees, Markov graphs, strongly connected digraphs
References
Bernhardt C.,Ho C.-W.,Morris C.,Kozerenko S.,Kozerenko S.,Larson C. E.,Pepper R.,Pavlenko V. A.,Pavlenko V. A.,Pavlenko V. A. .1989 .On characterization of periodic digraphs. Kibernetika, 25 : 49-54.
Sharkovsky O. M. .1964 .Coexistence of cycles of continuous mapping of the line into itself. Ukrainian Math. J, 16 : 61-71.
0

Citations

0

Downloads

77

Views