Document Open Access Logo

Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes

Authors Michael Drmota, Lander Ramos, Clément Requilé, Juanjo Rué

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.18.pdf
  • Filesize: 462 kB
  • 15 pages

Document Identifiers

Author Details

Michael Drmota
  • Institute of Discrete Mathematics and Geometry, Technisches Universität Wien, Austria.
Lander Ramos
  • Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain.
Clément Requilé
  • Institute for Algebra, Johannes Kepler Universität Linz, Austria.
Juanjo Rué
  • Departament de Matemàtiques, Universitat Politècnica de Catalunya and Barcelona Graduate School of Mathematics, Spain.

Funding

  • Drmota, Michael: Supported by the Special Research Program F50 Algorithmic and Enumerative Combinatorics of the Austrian Science Fund
  • Requilé, Clément: Supported by the Austrian Science Fund (FWF) grant F5004. Part of the work presented in this paper was carried out while the author was affiliated with the Institut für Mathematik und Informatik, Freie Universität Berlin, and Berlin Mathematical School, Germany, and partially supported by the FP7-PEOPLE-2013-CIG project CountGraph (ref. 630749).
  • Rué, Juanjo: Partially supported by the FP7-PEOPLE-2013-CIG project CountGraph (ref. 630749), the Spanish MICINN projects MTM2014-54745-P and MTM2017-82166-P and the María de Maetzu research grant MDM-2014-0445.

Cite AsGet BibTex

Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.18

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 series-parallel 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 Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Matchings and factors
  • Mathematics of computing → Trees
  • Mathematics of computing → Graph enumeration
Keywords
  • Asymptotic enumeration
  • central limit laws
  • subcritical graph classes
  • maximal independent set
  • maximal matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. François Bergeron, Gilbert Labelle, and Pierre Leroux. Combinatorial species and tree-like structures, volume 67. Cambridge University Press, 1998. Google Scholar
  2. Nicla Bernasconi, Konstantinos Panagiotou, and Angelika Steger. The degree sequence of random graphs from subcritical classes. Combinatorics, Probability and Computing, 18(5):647-681, 2009. Google Scholar
  3. Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Mathematics, 285:7-15, 2004. Google Scholar
  4. Michael Drmota. Random trees: an interplay between combinatorics and probability. SpringerWienNewYork, 2009. Google Scholar
  5. Michael Drmota, Éric Fusy, Mihyun Kang, Veronika Kraus, and Juanjo Rué. Asymptotic study of subcritical graph classes. SIAM J. Discrete Math., 25(4):1615-1651, 2011. Google Scholar
  6. Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, 2009. Google Scholar
  7. Agelos Georgakopoulos and Stephan Wagner. Limits of subcritical random graphs and random graphs with excluded minors. Available on-line on arXiv:1512.03572. Google Scholar
  8. Ian P. Goulden and David M. Jackson. Combinatorial enumeration. A Wiley-Interscience Publication. John Wiley &Sons, Inc., New York, 1983. Google Scholar
  9. Jerold R. Griggs, Charles M. Grinstead, and David R. Guichard. The number of maximal independent sets in a connected graph. Discrete Mathematics, 68:211-220, 1988. Google Scholar
  10. Joanna Górska and Zdzisław Skupień. Trees with maximum number of maximal matchings. Discrete Mathematics, 307:1367-1377, 2007. Google Scholar
  11. Clemens Heuberger and Stephan Wagner. The number of maximum matchings in a tree. Discrete Mathematics, 311(21):2512-2542, 2011. Google Scholar
  12. Min-Jen Jou and Gerard J. Chang. The number of maximum independent sets in graphs. Taiwanese Journal of Mathematics, 4(4):685-695, 2000. Google Scholar
  13. Amram Meir and John W. Moon. On maximal independent sets of nodes in trees. Journal of Graph Theory, 12(2):265-283, 1988. Google Scholar
  14. Konstantinos Panagiotou, Benedikt Stufler, and Kerstin Weller. Scaling limits of random graphs from subcritical classes. Ann. Probab., 44(5):3291-3334, 09 2016. URL: http://dx.doi.org/10.1214/15-AOP1048.
  15. Bruce E. Sagan. A note on independent sets in trees. SIAM Journal on Algebraic Discrete Methods, 1(1):105-108, 1988. Google Scholar
  16. William T. Tutte. Connectivity in graphs, volume 285. University of Toronto Press, 1966. Google Scholar
  17. Herbert S. Wilf. The number of maximal independent sets in a tree. SIAM Journal on Algebraic Discrete Methods, 7(1):125-130, 1986. Google Scholar
  18. Iwona Włoch. Trees with extremal numbers of maximal independent sets including the set of leaves. Discrete Mathematics, 308:4768-4772, 2008. Google Scholar
  19. Jennifer Zito. The structure and maximum number of maximum independent sets in trees. Journal of Graph Theory, 15(2):207-221, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact