Totally bounded ultrametric spaces generated by labeled rays

Oleksiy Dovgoshey

https://orcid.org/0000-0001-9689-2303

Ukraine

National Academy of Sciences of Ukraine image/svg+xml

Submitted: 2024-02-28

|

Accepted: 2024-11-27

|

Published: 2025-04-01

DOI: https://doi.org/10.4995/agt.2025.21269

Copyright (c) 2025 Oleksiy Dovgoshey, Valentino Vito

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Funding Data

Downloads

Keywords:

Cauchy sequence, labeled tree, ray, totally bounded ultrametric space

Supporting agencies:

Academy of Finland

Abstract:

We will say that a tree T is almost a ray if T is the union of a ray and a finite tree. Let l be a non-degenerate labeling of the vertex set V of almost a ray T and let dI be the corresponding ultrametric on V. It is shown that the ultrametric space (V, dI ) is totally bounded iff this space contains an infinite totally bounded subspace. We also prove that the last property characterizes the almost rays.

Show more Show less

References:

V. N. Berestrovskii, On Urysohn's $mathbb{R}$ tree, Siberian Mathematical Journal 60 (2019), no. 1, 10-19. https://doi.org/10.1134/S0037446619010026

V. Bilet, O. Dovgoshey, and Y. Kononov, Ultrametrics and complete multipartite graphs, Theory and Applications of Graphs 9 (2023), no. 1, Article 8. https://doi.org/10.20429/tag.2022.090108

H. Bruhn and R. Diestel, Duality in infinite graphs, Combinatorics, Probability and Computing 15 (2006), 75-90. https://doi.org/10.1017/S0963548305007261

H. Bruhn, R. Diestel, and M. Stein, Cycle-codycle partitions and faithfulcycle covers for locally finite graphs, Journal of Graph Theory 50 (2005), 150-161. https://doi.org/10.1002/jgt.20101

H. Bruhn and M. Stein, Duality of ends, Combinatorics, Probability and Computing 19 (2010), no. 1, 47-60. https://doi.org/10.1017/S0963548309990320

J. Cáceres, A. Márquez, O. R. Oellermann, and M. L. Puertas, Rebuilding convex sets in graphs, Discrete Math. 297 (2005), 26-37. https://doi.org/10.1016/j.disc.2005.03.020

S. R. Canoy Jr. and I. J. L. Garces, Convex sets under some graph operations, Graphs Comb. 4 (2002), 787-793. https://doi.org/10.1007/s003730200065

G. Chartrand, C. E. Wall, and P. Zhang, The convexity number of a graph, Graphs Comb. 18 (2002), 209-217. https://doi.org/10.1007/s003730200014

A. B. Comicheo and K. Shamseddine, Summary on non-Archimedean valued fields, Advances in Ultrametric Analysis (A. Escassut, C. Perez-Garcia, and K. Shamseddine, eds.), Contemporary Mathematics, vol. 704, Amer. Math. Soc. Providence, RI, 2018, pp. 1-36.

S. A. Cook, The complexity of theorem-proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 1971, pp. 151-158. https://doi.org/10.1145/800157.805047

R. Diestel, End spaces and spanning trees, Journal of Combinatorial Theory, Series B 96 (2006), no. 6, 846-854. https://doi.org/10.1016/j.jctb.2006.02.010

R. Diestel, Locally finite graphs with ends: A topological approach, I. Basic theory, Discrete Mathematics 311 (2011), no. 15, 1423-1447. https://doi.org/10.1016/j.disc.2010.05.023

R. Diestel, Ends and Tangles, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87 (2017), 223-244. https://doi.org/10.1007/s12188-016-0163-0

R. Diestel, Graph Theory, fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. https://doi.org/10.1007/978-3-662-53622-3_7

R. Diestel and D. Kühn, Topological paths, cycles and spanning trees in infinite graphs, Eur. J. Comb. 25 (2004), 835-862. https://doi.org/10.1016/j.ejc.2003.01.002

R. Diestel and J. Pott, Dual trees must share their ends, Journal of Combinatorial Theory, Series B 123 (2017), 32-53. https://doi.org/10.1016/j.jctb.2016.11.005

R. Diestel and P. Sprüssel, The fundamental group of a locally finite graph with ends, Advances in Mathematics 226 (2011), no. 3, 2643-2675. https://doi.org/10.1016/j.aim.2010.09.008

R. Diestel and P. Sprüssel, On the homology of locally compact spaces with ends, Topology and its Applications 158 (2011), no. 13, 1626-1639. https://doi.org/10.1016/j.topol.2011.05.031

R. Diestel and P. Sprüssel, Locally finite graphs with ends: A topological approach, III. Fundamental group and homology, Discrete Mathematics 312 (2012), no. 1, 21-29. https://doi.org/10.1016/j.disc.2011.02.007

O. Dovgoshey, Isomorphism of trees and isometry of ultrametric spaces, Theory and Applications of Graphs 7 (2020), no. 2, Article 3. https://doi.org/10.20429/tag.2020.070203

O. Dovgoshey, Strongly ultrametric preserving functions, Topology and its Applications 351 (2024), 108931. https://doi.org/10.1016/j.topol.2024.108931

O. Dovgoshey and M. Küc{c}ükaslan, Labeled trees generating complete, compact, and discrete ultrametric spaces, Ann. Comb. 26 (2022), 613-642. https://doi.org/10.1007/s00026-022-00581-8

O. Dovgoshey, O. Martio, and M. Vuorinen, Metrization of weighted graphs, Ann. Comb. 17 (2013), 455-476. https://doi.org/10.1007/s00026-013-0192-7

O. Dovgoshey and E. Petrov, Subdominant pseudoultrametric on graphs, Sb. Math 204 (2013), no. 8, 1131-1151. https://doi.org/10.1070/SM2013v204n08ABEH004333

O. Dovgoshey and E. Petrov, On some extremal properties of finite ultrametric spaces, p-adic Numbers Ultrametr. Anal. Appl. 12 (2020), no. 1, 1-11. https://doi.org/10.1134/S207004662001001X

O. Dovgoshey, E. Petrov, and H.-M. Teichert, On spaces extremal for the Gomory-Hu inequality, p-adic Numbers Ultrametr. Anal. Appl. 7 (2015), no. 2, 133-142. https://doi.org/10.1134/S2070046615020053

O. Dovgoshey, E. Petrov, and H.-M. Teichert, How rigid the finite ultrametric spaces can be?, Fixed Point Theory Appl. 19 (2017), no. 2, 1083-1102. https://doi.org/10.1007/s11784-016-0329-5

O. Dovgoshey and V. Shcherbak, The range of ultrametrics, compactness, and separability, Topology and its Applications 305 (2022), 107899. https://doi.org/10.1016/j.topol.2021.107899

M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986), 433-444. https://doi.org/10.1137/0607049

J. A. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics (2019), (Dynamic Survey DS6). https://doi.org/10.37236/27

J. G. Gimbel, Some remarks on the convexity number of a graph, Graphs Comb. 19 (2003), 357-361. https://doi.org/10.1007/s00373-002-0518-4

V. Gurvich and M. Vyalyi, Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs, Discrete Appl. Math. 160 (2012), no. 12, 1742-1756. https://doi.org/10.1016/j.dam.2012.03.034

F. Harary and J. Nieminen, Convexity in graphs, J. Differential Geom. 16 (1981), 185-190. https://doi.org/10.4310/jdg/1214436096

Y. Ishiki, An embedding, an extension, and an interpolation of ultrametrics, p-adic Numbers Ultrametr. Anal. Appl. 13 (2021), no. 2, 117-147. https://doi.org/10.1134/S2070046621020023

B. K. Kim, A lower bound for the convexity number of some graphs, J. Appl. Math. Comput. 14 (2003), 185-191. https://doi.org/10.1007/BF02936107

A. J. Lemin, On Gelgfand's problem concerning graphs, lattices, and ultrametric spaces, AAA62 Workshop on General Algebra -- 62. Arbeitstagung Allgemeine Algebra (Linz, Austria), June 2001, pp. 12-13.

F. Mémoli, A. Munk, Zh. Wan, and Ch. Weitkamp, The ultrametric Gromov--Wasserstein distance, Discrete Comput. Geom. 70 (2023), no. 4, 1378-1450. https://doi.org/10.1007/s00454-023-00583-0

I. M. Pelayo, Geodesic convexity in graphs, SpringerBriefs Math., Springer New York, NY, 2013. https://doi.org/10.1007/978-1-4614-8699-2

C. Perez-Garcia and W. H. Schikhof, Locally Convex Spaces over Non-Archimedean Valued Fields, Cambridge Studies in Advanced Mathematics, vol. 119, Cambridge University Press, Cambridge, 2010. https://doi.org/10.1017/CBO9780511729959

E. Petrov and A. Dovgoshey, On the Gomory-Hu inequality, J. Math. Sci. 198 (2014), no. 4, 392-411, Translation from Ukr. Mat. Visn. 10, no. 4 (2013), 469-496. https://doi.org/10.1007/s10958-014-1798-y

M. Ó. Searcóid, Metric Spaces, Springer--Verlag, London, 2007.

Show more Show less