Generalizing Tutte¡¯s theorem and maximal non-matchable graphs

详细信息    查看全文

• 作者：Cheng Yeaw Ku ; Kok Bin Wong
• 关键词：Matching polynomial ; Gallai&ndash ; Edmonds decomposition ; Maximal non-matchable graphs ; Tutte&rsquo ; s theorem
• 刊名：Discrete Mathematics
• 出版年：2013
• 出版时间：28 October, 2013
• 年：2013
• 卷：313
• 期：20
• 页码：2162-2167
• 全文大小：373 K

文摘

A graph has a perfect matching if and only if is not a root of its matching polynomial . Thus, Tutte¡¯s famous theorem asserts that is not a root of if and only if for all , where denotes the number of odd components of . Tutte¡¯s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte¡¯s theorem in terms of avoiding any given real number as a root of . We also extend maximal non-matchable graphs to maximal -non-matchable graphs and determine the structure of such graphs.