On strongly connected Markov graphs of maps on combinatorial trees
Loading...
Date
2025
Authors
Kozerenko, Sergiy
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
trees, permutations, Markov graphs, strongly connected digraphs, article
Citation
Kozerenko S. On strongly connected Markov graphs of maps on combinatorial trees / Sergiy Kozerenko // Discrete Mathematics Letters. - 2025. - Vol. 15. - P. 31-38. - https://doi.org/10.47443/dml.2024.218