|
Title:
|
Maximal independent sets and maximal matchings in series-parallel and related graph classes
|
|
Author:
|
Drmota, Michael; Ramos, Lander; Requilé, Clément; Rué Perna, Juan José
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics |
|
Abstract:
|
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in seriesparallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística
-Combinatorial analysis
-asymptotic enumeration
-central limit laws
-subcritical graph classes
-maximal independent set
-maximal matching
-Anàlisi combinatòria |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Conference Object |
|
Published by:
|
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
|
|
Share:
|
|
