Chebyshevskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Chebyshevskii Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Chebyshevskii Sbornik, 2024, Volume 25, Issue 3, Pages 101–117
DOI: https://doi.org/10.22405/2226-8383-2024-25-3-101-117
(Mi cheb1448)
 

This article is cited in 1 scientific paper (total in 1 paper)

Existence of irreducible multitours of multiplicity $2$

A. O. Ivanovab, O. S. Shcherbakovabc

a Lomonosov Moscow State University (Moscow)
b Bauman Moscow State Technical University (Moscow)
c University Gymnasium (Moscow)
Full-text PDF (880 kB) Citations (1)
Abstract: Ivanov and Tuzhilin stated the problem of one-dimensional Gromov minimal filling of finite metric spaces, where the filling is considered as a weighted connected graph containing the metric space as a subset of its vertex set. They shown that the problem can be always reduced to the case of so-called binary trees — trees whose vertices have degrees $1$ and $3$ only. Later Eremin obtained a minimax formula for the weight of the minimal filling. Eremin's formula uses the concept of minimum parametric filling, i.e. the filling with a fixed graph (parameterization or type), and the weight of the minimal parametric filling turns out to be equal to the maximum value of so-called multi-perimeters over all irreducible multi-tours.
Moustaches of a binary tree is a pair of its vertices of degree $1$ having a common adjacent vertex. The number of moustaches can measure complexity of binary trees. In this paper the multi-tours of binary trees with $3$ moustaches are investigated. A linear recurrent formula is found for the number of such binary trees. For a fixed binary tree a connection is established between the irreducibility of multi-tours and inclusions of multi-tours multi-graphs.
Recently Shcherbakov proved that the multiplicity of an irreducible multi-tour for a binary tree with $3$ moustaches does not exceed $2$; in this paper the existence of such irreducible multi-tour for any binary tree with $3$ moustaches is proved.
Ivanov and Tuzhilin proposed to calculate the weight of a minimal parametric filling by finding the vertices of a multidimensional polyhedron of feasible variable values of the dual linear programming problem. These their results are based on computer calculations. The technique developed in this paper permits to find all irreducible multi-tours of a binary tree with $6$ boundary vertices and $3$ moustaches without a computer.
Keywords: finite metric space, minimal parametric filling, linear programming, convex polytops of binary tree, irreduceble multi-torus, multigraph of multi-torus.
Received: 10.04.2024
Accepted: 04.09.2024
Document Type: Article
UDC: 515.124.4+519.852.3
Language: Russian
Citation: A. O. Ivanov, O. S. Shcherbakov, “Existence of irreducible multitours of multiplicity $2$”, Chebyshevskii Sb., 25:3 (2024), 101–117
Citation in format AMSBIB
\Bibitem{IvaShc24}
\by A.~O.~Ivanov, O.~S.~Shcherbakov
\paper Existence of irreducible multitours of multiplicity $2$
\jour Chebyshevskii Sb.
\yr 2024
\vol 25
\issue 3
\pages 101--117
\mathnet{http://mi.mathnet.ru/cheb1448}
\crossref{https://doi.org/10.22405/2226-8383-2024-25-3-101-117}
Linking options:
  • https://www.mathnet.ru/eng/cheb1448
  • https://www.mathnet.ru/eng/cheb/v25/i3/p101
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025