On the number of spanning trees in directed circulant graphs

Let g k ( n ) [respectively, f k ( n )] be the maximum number of spanning trees in directed circulant graphs (respectively, regular directed graphs) with n vertices and out‐degrees equal to k > 1. We show that g k ( n ) = k n (1+ o (1)) and f k ( n ) = k n (1+ o (1)) . Moreover, we prove that g 2 ( n ) = ⌊(2 n + 1)/3⌋. © 2001 John Wiley & Sons, Inc.