Random graphs from a block-stable class

DOI10.1016/J.EJC.2016.05.005MaRDI QIDQ739054zbMATH OpenOpenAlexFDO

Authors Colin McDiarmid, Alex Scott

Publication date 16 August 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

weakly block-stable classes of graphs

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A class of graphs is called block-stable when a graph is in the class if and only if each of its blocks is. We show that, as for trees, for most $n$-vertex graphs in such a class, each vertex is in at most $(1+o(1))logn/loglogn$ blocks, and each path passes through at most $5(nlogn{)}^{1/2}$ blocks. These results extend to `weakly block-stable' classes of graphs.

Recommendations

• Blocks in constrained random graphs with fixed average degree
• Random graphs with few disjoint cycles
• Maximal biconnected subgraphs of random planar graphs
• Maximal biconnected subgraphs of random planar graphs
• Random graphs from a minor-closed class

Cites work

• 3-Connected Cores In Random Planar Graphs
• A course in combinatorics.
• An extension of the Prüfer code and assembly of connected graphs from their blocks
• Asymptotic enumeration and limit laws of planar graphs
• Asymptotic study of subcritical graph classes
• Connectivity for Bridge-addable monotone graph classes
• Counting planar graphs and related families of graphs
• Extremal Parameters in Sub-Critical Graph Classes
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Maximal biconnected subgraphs of random planar graphs
• Maximum degree in minor-closed classes of graphs
• On the connectivity of random graphs from addable classes
• On the diameter of random planar graphs
• On the height of trees
• On the maximum degree in a random tree
• On the Maximum Degree of a Random Planar Graph
• Random graphs from a minor-closed class
• Random planar graphs
• Random planar graphs and beyond
• Random Trees
• Scaling limits of random graphs from subcritical classes
• The average height of binary trees and other simple trees
• The degree sequence of random graphs from subcritical classes
• The maximum degree in a random tree and related problems
• The maximum degree of random planar graphs

Cited in

(17)

• Limits of random tree-like discrete structures
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Asymptotic properties of random unlabelled block-weighted graphs
• On classes of infinite loaded graphs with randomly deleted edges
• Blocks in constrained random graphs with fixed average degree
• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• The second Riddell relation and its consequences
• On the number of labeled outerplanar k-cyclic bridgeless graphs
• Asymptotic enumeration of labeled series-parallel k-cyclic bridgeless graphs
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• scientific article; zbMATH DE number 7656033 (Why is no real title available?)
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
• Enumeration of labeled series-parallel tricyclic graphs
• Random trees have height \(O(\sqrt{n})\)
• Enumeration of labeled bi-block graphs
• On one approach to enumeration of labeled connected graphs: a review
• Asymptotical enumeration of labeled series-parallel tetracyclic graphs

This page was built for publication: Random graphs from a block-stable class

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