Graphs with the fewest matchings

详细信息    查看全文

• 作者：Lauren Keough ; Andrew J. Radcliffe
• 关键词：Mathematics Subject Classification (2000)05C30
• 刊名：Combinatorica
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：36
• 期：6
• 页码：703-723
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Mathematics, general;
• 出版者：Springer Berlin Heidelberg
• ISSN：1439-6912
• 卷排序：36

文摘

In recent years there has been increased interest in extremal problems for “counting” parameters of graphs. For example, the Kahn-Zhao theorem gives an upper bound on the number of independent sets in a d-regular graph. In the same spirit, the Upper Matching Conjecture claims an upper bound on the number of k-matchings in a d-regular graph. Here we consider both matchings and matchings of fixed sizes in graphs with a given number of vertices and edges. We prove that the graph with the fewest matchings is either the lex or the colex graph. Similarly, for fixed k, the graph with the fewest k-matchings is either the lex or the colex graph. To prove these results we first prove that the lex bipartite graph has the fewest matchings of all sizes among bipartite graphs with fixed part sizes and a given number of edges.