Premium
On the number of spanning trees in directed circulant graphs
Author(s) -
Lonc Zbigniew,
Parol Krzysztof,
Wojciechowski Jacek M.
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.2
Subject(s) - circulant matrix , combinatorics , spanning tree , mathematics , discrete mathematics
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.