Key points are not available for this paper at this time.
Abstract Let G be a vertex-weighted connected graph of n vertices and let T be a spanning tree of G. We call T a maximum weighted internal spanning tree of G if the sum of the weights of the internal vertices of T is the maximum over all spanning trees of G. The maximum weighted internal spanning tree (MaxwIST) problem asks to find such a spanning tree T of G. The problem is NP-hard. We give an O (dn) time approximation algorithm for d-regular graphs of n=|V| vertices that computes a spanning tree with total weight of the internal vertices is at least ₃ ₃ +d-2 - of the total weight of all the vertices of the graph for any 0, where ₃ = (d-1) H₃-₁, and H₃-₁ = ₈=₁^d-1 i^-1 is the (d-1) th harmonic number. For every d 3 and n₀ 1, we show the construction of a d-regular graph of at least n₀ vertices, such that for any of its spanning trees, w (I) w (V) dd+1 holds. We give an O (dn) time approximation algorithm for subdivisions of d-regular graphs, where the ratio of the internal weight of the spanning tree with the total vertex weight of the graph is at least d-12d-3 - for 0. We extend our study to x-subdivisions of Hamiltonian and hypoHamiltonian graphs, where each edge of the original Hamiltonian or hypoHamiltonian graph has been subdivided at least x times. For those two graph classes, we show that there exists a spanning tree with internal vertex weight at least 1-2x-1 of the total vertex weight of the graph. Furthermore, we give O (n) time algorithm for x-subdivisions of biconnected outerplanar graphs and 4-connected planar graphs to achieve the above bound.
Hakim et al. (Thu,) studied this question.