In this work, we address two variants of the spanning tree problem. The first problem deals with finding a spanning tree such that the number of branch vertices,vertices with degrees of at least three, is minimum (MBV) and the second one involves constructing a spanning tree with minimum sum of branch vertex degrees (MDS). We suggest an attribute based Tabu Search (TS) heuristic approach for both problems. According to extensive computational experiments done on standard test sets, we observe that the TS heuristics outperform the best known heuristics from the literature. (C) 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.