On Central Spanning Trees of a Graph

We consider the collection of all spanning trees of a graph with distance between them based on the size of the symmetric difference of their edge sets. A central spanning tree of a graph is one for which the maximal distance to all other spanning trees is minimal. We prove that the problem of constructing a central tree is algorithmically difficult and leads to an NP-complete problem. 1 Introduction All the basic notions concerning graphs, which are not explained here, may be found in any introductory book on graph theory, e.g. [4]. In the whole paper we consider undirected connected graphs without loops, but maybe with multiple edges. For a graph G we denote by V (G) and E(G) its vertex and edge sets, respectively. Let T 1 and T 2 be a pair of spanning trees of a graph G. We define the distance between T 1 and T 2 as D(T 1 ; T 2 ) = 1 2 \Delta j(E(T 1 ) [ E(T 2 )) n (E(T 1 ) " E(T 2 ))j; i.e. the distance equals half of the symmetric difference between E(T 1 ) and E(T 2 ) (notice..