Opuscula Math. 41, no. 1 (2021), 55-70

Opuscula Mathematica

More on linear and metric tree maps

Sergiy Kozerenko

Abstract. We consider linear and metric self-maps on vertex sets of finite combinatorial trees. Linear maps are maps which preserve intervals between pairs of vertices whereas metric maps are maps which do not increase distances between pairs of vertices. We obtain criteria for a given linear or a metric map to be a positive (negative) under some orientation of the edges in a tree, we characterize trees which admit maps with Markov graphs being paths and prove that the converse of any partial functional digraph is isomorphic to a Markov graph for some suitable map on a tree.

Keywords: tree, Markov graph, metric map, non-expanding map, linear map, graph homomorphism.

Mathematics Subject Classification: 05C05, 05C12, 05C20, 54E40.

Full text (pdf)

  1. H.-J. Bandelt, M. van de Vel, A fixed cube theorem for median graphs, Discrete Math. 67 (1987), 129-137.
  2. S. Kozerenko, Markov graphs of one-dimensional dynamical systems and their discrete analogues, Rom. J. Math. Comput. Sci. 6 (2016), 16-24.
  3. S. Kozerenko, Discrete Markov graphs: loops, fixed points and maps preordering, J. Adv. Math. Stud. 9 (2016), 99-109.
  4. S. Kozerenko, On the abstract properties of Markov graphs for maps on trees, Mat. Bilten 41 (2017), 5-21.
  5. S. Kozerenko, On disjoint union of M-graphs, Algebra Discrete Math. 24 (2017), 262-273.
  6. S. Kozerenko, Linear and metric maps on trees via Markov graphs, Comment. Math. Univ. Carolin. 59 (2018), 173-187.
  7. R. Nowakowski, I. Rival, Fixed-edge theorem for graphs with loops, J. Graph Theory 3 (1979), 339-350.
  8. R. Nowakowski, I. Rival, On a class of isometric subgraphs of a graph, Combinatorica 2 (1982), 77-88.
  9. A. Quilliot, A retraction problem in graph theory, Discrete Math. 54 (1985), 61-71.
  10. E. Wilkeit, Graphs with regular endomorphism monoid, Arch. Math. 66 (1996), 344-352.
  11. T. Zamfirescu, Non-expanding mappings in graphs, Adv. Appl. Math. Sci. 6 (2010), 23-32.
  • Sergiy Kozerenko
  • ORCID iD https://orcid.org/0000-0002-5716-3084
  • National University of Kyiv-Mohyla Academy, Department of Mathematics, Faculty of Informatics, 04070, Skovorody Str. 2, Kyiv, Ukraine
  • Communicated by Andrzej Żak.
  • Received: 2019-08-09.
  • Revised: 2020-12-23.
  • Accepted: 2020-12-28.
  • Published online: 2021-02-08.
Opuscula Mathematica - cover

Cite this article as:
Sergiy Kozerenko, More on linear and metric tree maps, Opuscula Math. 41, no. 1 (2021), 55-70, https://doi.org/10.7494/OpMath.2021.41.1.55

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.