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:
|
|