License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.24
URN: urn:nbn:de:0030-drops-120543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12054/
Go to the corresponding LIPIcs Volume Portal

Ralaivaosaona, Dimbinaina ; Requilé, Clément ; Wagner, Stephan

Block Statistics in Subcritical Graph Classes

pdf-format:
LIPIcs-AofA-2020-24.pdf (0.4 MB)

Abstract

We study block statistics in subcritical graph classes; these are statistics that can be defined as the sum of a certain weight function over all blocks. Examples include the number of edges, the number of blocks, and the logarithm of the number of spanning trees. The main result of this paper is a central limit theorem for statistics of this kind under fairly mild technical assumptions.

BibTeX - Entry

@InProceedings{ralaivaosaona_et_al:LIPIcs:2020:12054,
  author =	{Dimbinaina Ralaivaosaona and Cl{\'e}ment Requil{\'e} and Stephan Wagner},
  title =	{{Block Statistics in Subcritical Graph Classes}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Michael Drmota and Clemens Heuberger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12054},
  URN =		{urn:nbn:de:0030-drops-120543},
  doi =		{10.4230/LIPIcs.AofA.2020.24},
  annote =	{Keywords: subcritical graph class, block statistic, number of blocks, number of edges, number of spanning trees}
}

Keywords: subcritical graph class, block statistic, number of blocks, number of edges, number of spanning trees
Collection: 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Issue Date: 2020
Date of publication: 10.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI