A generalized optimum requirement spanning tree problem with a Monge-like property

We consider a generalized optimum requirement spanning tree problem (GORST problem) which is an extension of the problem studied by Hu. In the GORST problem, the degrees of vertices are restricted and the objective function is generalized. We will show that a particular tree T*, which is obtained by a sort of greedy algorithm but is explicitly definable, is a solution to the GORST problem when a condition similar to the Monge property is satisfied. Also, we will define a problem of finding a tree network which minimizes the probability that a request of communication is not realized when the network has k failures (called a ‘k-failure problem’), and show that T* is an explicit solution to the k-failure problem for any k when the maximum degree constraint is imposed and the Monge-like property is satisfied.