On Universal Graphs for Spanning Trees

Abstract

A number of papers [1,2,3,4,6] recently have been concerned with the following question. What is the minimum number s{n) of edges a graph G on n vertices can have so that any tree on n vertices is isomorphic to some spanning tree of G? We call such a graph universal for spanning trees. Since Kn, the complete graph