|
Título:
|
Maximal independent sets and maximal matchings in series-parallel and related graph classes
|
|
Autor/a:
|
Drmota, Michael; Ramos, Lander; Requilé, Clément; Rué Perna, Juan José
|
|
Otros autores:
|
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. |
|
Materia(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 |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Objeto de conferencia |
|
Editor:
|
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
|
|
Compartir:
|
|
