[Zurück]


Zeitschriftenartikel:

M. Drmota, L. Ramos, C. Requilé, J. Rué:
"Maximal independent sets and maximal matchings in series-parallel and related graph classes";
Electronic Journal of Combinatorics, 27 (2020), 1.



Kurzfassung englisch:
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].


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.37236/8683


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.