| Abstract: | In this paper, we consider the problem of finding the graph topology of p vertices and q edges such that the resulting graph contains the maximum number of spanning trees. For any values of p and q, this problem still remains open. Only when q≧ p(p? l)/2 ? [p/2] it has been solved by Shier [4] and, recently, when q = p+1 it has been solved by Wang and Wu [5]. In this paper, we shall formulate this problem into a nonlinear integer program by using the properties of the cycle bases of graphs. And then we shall show that this nonlinear integer program can be easily solved when q = p+ 1 by applying our cycle basis approach. Consequently, we shall solve the nonlinear integer program when q =p + 2. Finally, concluding remarks will be given. |
