On the characterization of graphs with maximum number of spanning trees Original Research Article

A graph G with n nodes and e edges is said to be t-optimal if G has the maximum number of spanning trees among all graphs with the same number of nodes and edges as G. Hitherto, t-optimal graphs have been characterized for the following cases: 1. (a) n = sp, and e = (s(s - 1)/2)p2, when s and p are positive integers, and s > 1; 2. (b) e ⩽ n + 2; 3. (c) e ⩾ n(n - 1)/2 - n/2. In this paper we use algebraic techniques involving eigenvalues to determine t-optimal graphs for e ⩾ n(n - 1)/2 - n + 2. This range is extended to include e = n(n - 1)/2 - n + 1 and e = n(n - 1)/2 - n, provided n(n - 1)/2 - e is a multiple of three.