Spanning trees in random series-parallel graphs

DOI10.1016/J.AAM.2015.12.001MaRDI QIDQ256329zbMATH OpenOpenAlexFDO

Authors Julia Ehrenmüller, Juanjo Rué

Publication date 9 March 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.01922

zbMATH Keywords

analytic techniquesspanning trees in a connected labelled series-parallel graph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on $n$ vertices chosen uniformly at random satisfies an estimate of the form $svarrh{o}^{-n}(1+o(1))$, where $s$ and $varrho$ are computable constants, the values of which are approximately $sapprox0.09063$ and $varrh{o}^{-1}approx2.08415$. We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.

Recommendations

• scientific article; zbMATH DE number 747032
• Spanning trees in random graphs
• Spanning trees in randomly perturbed graphs
• Spanning trees in random regular uniform hypergraphs
• On the number of spanning trees in random regular graphs
• scientific article; zbMATH DE number 17672
• Trees in sparse random graphs
• Spanning trees and random walks on weighted graphs
• Spanning trees in random satisfiability problems
• Spanning trees of finite Sierpiński graphs

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 3150821 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• A characterization of the Tutte polynomial via combinatorial embeddings
• A complete grammar for decomposing a family of graphs into 3-connected components
• Analytic combinatorics
• Asymptotic Enumeration of Spanning Trees
• Asymptotic enumeration and limit laws of planar graphs
• Asymptotic enumeration of non-crossing partitions on surfaces
• Asymptotic study of subcritical graph classes
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Enumerating simplicial decompositions of surfaces with boundaries
• Enumeration and limit laws for series-parallel graphs
• Extremal Parameters in Sub-Critical Graph Classes
• Graph Classes: A Survey
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Handbook of Enumerative Combinatorics
• On convergence rates in the central limit theorems for combinatorial structures
• On the Enumeration of Tree-Rooted Maps
• On the probability of planarity of a random graph near the critical point
• Random Trees
• Random cubic planar graphs
• Scaling limits of random graphs from subcritical classes: extended abstract
• Shuffle of parenthesis systems and Baxter permutations
• Singularity Analysis of Generating Functions
• Spanning forests in regular planar maps
• Spanning trees in regular graphs
• The birth of the giant component
• The degree sequence of random graphs from subcritical classes
• The maximum degree of series-parallel graphs
• The number of connected sparsely edged graphs
• The number of connected sparsely edged graphs. II. Smooth graphs and blocks
• The number of spanning trees in graphs with a given degree sequence
• The number of spanning trees in regular graphs
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Two critical periods in the evolution of random planar graphs
• Vertices of given degree in series-parallel graphs

Cited in

(6)

• Limits of random tree-like discrete structures
• On the number of series parallel and outerplanar graphs
• Enumeration and limit laws for series-parallel graphs
• On the combinatorics of binary series-parallel graphs
• The Merino-Welsh conjecture holds for series-parallel graphs
• The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs

This page was built for publication: Spanning trees in random series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q256329)