Existence of irreducible multitours of multiplicity 2

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 multitour 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.