Geodesic
Maximal independent sets and maximal matchings in series-parallel and related graph classes
Michael Drmota1 ; Lander Ramos2 ; Clément Requilé1 ; Juanjo Rué2
1Technische Universität Wien
2Universitat Politècnica de Catalunya
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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].
DOI : 10.37236/8683
Classification : 05C69, 05C30, 05C70, 05C80, 05C35
Mots-clés : cacti graphs, series-parallel graphs

Michael Drmota  1   ; Lander Ramos  2   ; Clément Requilé  1   ; Juanjo Rué  2

1 Technische Universität Wien
2 Universitat Politècnica de Catalunya 
@article{10_37236_8683,
     author = {Michael Drmota and Lander Ramos and Cl\'ement Requil\'e and Juanjo Ru\'e},
     title = {Maximal independent sets and maximal matchings in series-parallel and related graph classes},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8683},
     zbl = {1431.05112},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8683/}
}
TY  - JOUR
AU  - Michael Drmota
AU  - Lander Ramos
AU  - Clément Requilé
AU  - Juanjo Rué
TI  - Maximal independent sets and maximal matchings in series-parallel and related graph classes
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8683/
DO  - 10.37236/8683
ID  - 10_37236_8683
ER  - 
%0 Journal Article
%A Michael Drmota
%A Lander Ramos
%A Clément Requilé
%A Juanjo Rué
%T Maximal independent sets and maximal matchings in series-parallel and related graph classes
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8683/
%R 10.37236/8683
%F 10_37236_8683
Michael Drmota; Lander Ramos; Clément Requilé; Juanjo Rué. Maximal independent sets and maximal matchings in series-parallel and related graph classes. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8683

Cité par Sources :