Discrete Applied Math Seminar by Gunjan Sharma: "Almost-Perfect Matchings in Trees"

Speaker: Gunjan Sharma, Illinois Institute of Technology

Title: Almost-Perfect Matchings in Trees

Abstract: The Hosoya index of a graph is the total number of matchings in it and is a long-studied graph invariant. Among trees of a fixed order, it is known that the Hosoya index is maximized by the path and minimized by the star. Moreover, the path maximizes the number of matchings of any fixed size. We consider extremal problems for two types of matchings in trees of order n: almost-perfect matchings, which cover all but one vertex when n is odd and all but two vertices when n is even; and strong almost-perfect matchings, which are almost-perfect matchings such that the vertices which are not covered are leaves. We characterize the maximizing trees for both these matching types. We also determine the trees that minimize the number of maximal matchings. We apply these results to prove extremal results for the weighted Hosoya index for several natural choices of vertex-degree-based weight function.

This is joint work with Stijn Cambie, Bradley McCoy, Stephan Wagner and Corrine Yap.

 

Discrete Applied Math Seminar

Request Zoom link