Ordering the complements of trees by the number of maximum matchings

摘要

A "perfect matching" of a graph G with n vertices is a set of [n/2] independent edges of G. In the present study, we succeeded in determining the trees whose complements have the extremal number of "perfect matchings" for two different group of trees. Some further problems are also posed. (c) 2005 Wiley Periodicals, Inc.