Search

The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and series-parallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]., Comment: 32 pages, 7 figures

Let $H$ be a fixed graph and $\mathcal{G}$ a subcritical graph class. In this paper we show that the number of occurrences of $H$ (as a subgraph) in a uniformly at random graph of size $n$ in $\mathcal{G}$ follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations. As a case study, we get explicit expressions for the number of triangles and cycles of length four for the family of series-parallel graphs., Comment: 32 pages, 6 figures

We study the uniform random graph $\mathsf{C}_{n}$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_{n}/\sqrt{n}$ converges to the Brownian continuum random tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide sub-Gaussian tail bounds for the diameter $\mathrm{D}(\mathsf{C}_{n})$ and height $\mathrm{H}(\mathsf{C}_{n}^{\bullet})$ of the rooted random graph $\mathsf{C}_{n}^{\bullet}$. We give analytic expressions for the scaling factor in several cases, including for example the class of outerplanar graphs. Our methods also enable us to study first passage percolation on $\mathsf{C}_{n}$, where we also show the convergence to $\mathcal{T}_{\mathsf{e}}$ under an appropriate rescaling.