|本期目录/Table of Contents|

[1]翟绍辉*,郭利涛,郑艺容,等.图的最大匹配个数的下界[J].厦门大学学报(自然科学版),2018,57(05):680-683.[doi:10.6043/j.issn.0438-0479.201712025]
 ZHAI Shaohui*,GUO Litao,ZHENG Yirong,et al.The Lower Bound on the Number of Maximum Matchings of a Graph[J].Journal of Xiamen University(Natural Science),2018,57(05):680-683.[doi:10.6043/j.issn.0438-0479.201712025]
点击复制

图的最大匹配个数的下界(PDF/HTML)
分享到:

《厦门大学学报(自然科学版)》[ISSN:0438-0479/CN:35-1070/N]

卷:
57卷
期数:
2018年05期
页码:
680-683
栏目:
研究论文
出版日期:
2018-09-27

文章信息/Info

Title:
The Lower Bound on the Number of Maximum Matchings of a Graph
文章编号:
0438-0479(2018)05-0680-04
作者:
翟绍辉*郭利涛郑艺容庄 蔚
厦门理工学院应用数学学院,福建 厦门 361024
Author(s):
ZHAI Shaohui*GUO LitaoZHENG YirongZHUANG Wei
School of Applied Mathematics,Xiamen University of Technlogy,Xiamen 361024,China
关键词:
最大匹配 因子临界图 Gallai-Edmonds结构定理
Keywords:
maximum matching factor-critical graphs Gallai-Edmonds structure theorem
分类号:
O 157.5
DOI:
10.6043/j.issn.0438-0479.201712025
文献标志码:
A
摘要:
设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.
Abstract:
Let G be a connected graph of order n and let k be the size of maximum matchings in G,where n≥2k+1.In this paper,we present that G contains at least n-2k+1 distinct maximum matchings.In addition,we characterize graphs that possess exactly n-2k+1 distinct maximum matchings.

参考文献/References:

[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,SKUPIENZ.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.

备注/Memo

备注/Memo:
收稿日期:2017-12-15 录用日期:2017-06-12
基金项目:国家自然科学基金(11301440); 福建省自然科学基金(2015J05017)
*通信作者:shzhai@xmut.edu.cn
引文格式:翟绍辉*,郭利涛,郑艺容,等.图的最大匹配个数的下界[J].厦门大学学报(自然科学版),2018,57(5):680-683.
Citation:ZHAI S H,GUO L T,ZHENG Y R,et al.The lower bound on the number of maximum matchings of a graph[J].J Xiamen Univ Nat Sci,2018,57(5):680-683.(in Chinese)
更新日期/Last Update: 1900-01-01