Premium
On the asymptotic behavior of the maximum number of spanning trees in circulant graphs
Author(s) -
Lonc Zbigniew,
Parol Krzysztof,
Wojciechowski Jacek M.
Publication year - 1997
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/(sici)1097-0037(199708)30:1<47::aid-net6>3.0.co;2-l
Subject(s) - circulant matrix , spanning tree , combinatorics , mathematics , circulant graph , discrete mathematics , graph , line graph , voltage graph
The following asymptotic estimation of the maximum number of spanning trees f k ( n ) in 2 k ‐regular circulant graphs ( k > 1) on n vertices is the main result of this paper: f k ( n ) = ((2 k )/( r k )) n (1+ o (1)) , where $r_k = \hbox{exp}\left[\sum^\infty_{s=1} [1/(2s(2k)^{2s})] \left(\matrix{2s\cr s\cr}\right) \sum_{j_{1}+\dots +j_{k}=s} \left(\matrix{s\cr j_{1},\dots, j_{k}\cr}\right)^2 \right].$ © 1997 John Wiley & Sons, Inc. Networks 30:47–56, 1997