Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs (Q1297626): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:08, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs |
scientific article |
Statements
Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs (English)
0 references
25 January 2000
0 references
The authors established asymptotic formulas for the number of spanning trees and the number of Eulerian trails in circulant digraphs and in circulant graphs. In particular, if \(T\) is the number of spanning trees and \(E\) is the number of Eulerian trails in any circulant digraph with \(p\) vertices and out-degree \(k\) then it is shown that \({1\over k}[T]^{{1\over p}}\sim 1\) and \({1\over k!}[E]^{{1\over p}}\sim 1\) for \(p\to\infty\). Additional results are established for line graphs and for circulant graphs.
0 references
asymptotic formulas
0 references
number of spanning trees
0 references
number of Eulerian trails
0 references
circulant digraphs
0 references
circulant graphs
0 references
line graphs
0 references