图的最大匹配个数的下界

详细信息    查看全文 | 推荐本文 |

英文篇名：The Lower Bound on the Number of Maximum Matchings of a Graph 作者：翟绍辉 ; 郭利涛 ; 郑艺容 ; 庄蔚 英文作者：ZHAI Shaohui;GUO Litao;ZHENG Yirong;ZHUANG Wei;School of Applied Mathematics,Xiamen University of Technlogy; 关键词：最大匹配 ; 因子临界图 ; Gallai-Edmonds结构定理 英文关键词：maximum matching;;factor-critical graphs;;Gallai-Edmonds structure theorem 中文刊名：XDZK 英文刊名：Journal of Xiamen University(Natural Science) 机构：厦门理工学院应用数学学院; 出版日期：2018-09-28 出版单位：厦门大学学报(自然科学版) 年：2018 期：v.57;No.266 基金：国家自然科学基金(11301440);; 福建省自然科学基金(2015J05017) 语种：中文; 页：XDZK201805014 页数：4 CN：05 ISSN：35-1070/N 分类号：94-97

摘要

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.
        Let Gbe a connected graph of order nand let kbe the size of maximum matchings in G,where n≥2 k+1.In this paper,we present that Gcontains at least n-2 k+1 distinct maximum matchings.In addition,we characterize graphs that possess exactly n-2 k+1 distinct maximum matchings.

引文

[1]BONDY J A,MURTY U S R.Graph theory with applications[M].New York:American Elsevier,1976:32-36.
    [2]LOVSZ L,PLUMMER M D.Matching theory[M].New York:North-Holland,1986:83-92.
    [3]PETERSEN J.Die theorie der regularen graphen[J].Acta Math,1891,15:193-220.
    [4]ESPERET L,KARDOS F,KING A D.Exponentially many perfect matchings in cubic graphs[J].Advances in Math,2011,227:1646-1664.
    [5]EDMONDS J,LOVSZ L,PULLEYBLANK W R.Brick decompositions and the matching rank of graphs[J].Combinatorica,1982,2(3):247-274.
    [6]LAURENT M,SCHRIJVER L.On leonid gurvits′proof for permanents[J].Amer Math Monthly,2010,117(10):903-911.
    [7]ESPERET L,KRL D,KODA P,et al.An improved linear bound on the number of perfect matchings in cubic graphs[J].European J Combin,2010,31:1316-1334.
    [8]GóRSKA J,SKUPIEN'Z.Trees with maximum number of maximal matchings[J].Discrete Math,2007,307:1367-1377.
    [9]HEUBERGER C,WAGNER S.The number of maximum matchings in a tree[J].Discrete Math,2011,311:2512-2542.
    [10]HALL P.On representatives of subsets[J].J London Math Soc,1935,10:26-30.