Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Trees maximizing the number of almost-perfect matchings
Katholieke Univ Leuven, Dept Comp Sci, Campus Kulak Kortrijk, Kortrijk, Belgium..
James Madison Univ, Dept Comp Sci, Harrisonburg, VA USA..
IIT, Appl Math, Chicago, IL USA..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Probability Theory and Combinatorics. Graz Univ Technol, Inst Discrete Math, Graz, Austria.ORCID iD: 0000-0001-5533-2764
Show others and affiliations
2025 (English)In: Applicable Analysis and Discrete Mathematics, ISSN 1452-8630, Vol. 19, no 1, p. 104-129Article in journal (Refereed) Published
Abstract [en]

We characterize the extremal trees that maximize the number of almost-perfect matchings, which are matchings covering all but one or two vertices, and those that maximize the number of strong almost-perfect matchings, which are matchings missing only one or two leaves. We also determine the trees that minimize the number of maximal matchings. We apply these results to extremal problems on the weighted Hosoya index for several choices of vertex-degree-based weight function.

Place, publisher, year, edition, pages
National Library of Serbia , 2025. Vol. 19, no 1, p. 104-129
Keywords [en]
Trees, Matching, Almost-perfect matching, Maximal matching, Weighted Hosoya index
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-556061DOI: 10.2298/AADM230824006CISI: 001476838200007OAI: oai:DiVA.org:uu-556061DiVA, id: diva2:1957334
Part of project
Analytic and probabilistic tools for the study of random trees, Swedish Research Council
Funder
Knut and Alice Wallenberg Foundation, KAW 2017.0112Swedish Research Council, 2022-04030Available from: 2025-05-09 Created: 2025-05-09 Last updated: 2025-05-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Wagner, Stephan

Search in DiVA

By author/editor
Wagner, Stephan
By organisation
Probability Theory and Combinatorics
In the same journal
Applicable Analysis and Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 54 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf