Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs
type: Item
instance of: scholarly article
title: Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs
zbMATH Open document ID: 0929.05018
DOI: 10.1007/BF02879060
published in: Science in China. Series A
publication date: 2000-01-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1329996
zbMATH Keywords: asymptotic formulas
zbMATH Keywords: number of spanning trees
zbMATH Keywords: number of Eulerian trails
zbMATH Keywords: circulant digraphs
zbMATH Keywords: circulant graphs
zbMATH Keywords: line graphs
author: Fuji Zhang
author: Xuerong Yong
reviewed by: David P. Brown
MaRDI profile type: Publication
cites work: A Combinatorial Problem Related to Multimodule Memory Organizations
cites work: An Algorithm for Non-Linear Network Programming: Implementation, Results and Comparisons
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Q5636912
cites work: On the number of spanning trees and Eulerian tours in iterated line digraphs
cites work: Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
cites work: Matching theory
cites work: Q4771385
cites work: An asymptotic property of the number of spanning trees of double fixed step loop networks
cites work: Roots and Canonical Forms for Circulant Matrices
cites work: Design to Minimize Diameter on Building-Block Network
cites work: A Design for Directed Graphs with Minimum Diameter
cites work: On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs
description: scientific article; zbMATH DE number 1329996