Résumé
Given a connected graph G = (V, E), a vertex v ∈ V is said to be a branch vertex if d(v) > 2, where d(v) denotes the degree of vertex v. The Minimum Branch Vertices Spanning Tree (MBVST) problem is to nd a spanning tree of G with the minimum number of branch vertices. This problem has been extensively studied in the literature and has welldeveloped applications notably related to routing in optical networks. In this paper, we propose a generalization of this problem, where we begin by introducing the notion of a k-branch vertex, which is a vertex with degree strictly greater than k + 2, and the goal is to determine a spanning tree of G with the minimum number of k-branch vertices (k-MBVST problem). In the context of optical networks, the parameter k can be seen as the limiting capacity of optical splitters to split the input light signal to k sub-trees. Proofs of NP-hardness and non-inclusion in the APX class of the k-MBVST problem are established for a generic value of k, and then an ILP formulation of the k-MBVST problem based on single commodity ow balance constraints is derived. Computational results based on randomly generated graphs show that the number of k-branch vertices included in the spanning tree increases with the size of the vertex set V, but decreases with k as well as graph density. We also show that when k ≥ 4, the number of k-branch vertices in the optimal solution is close to zero, regardless of the size and the density of the underlying graph.