最大匹配的路变换图

doi:10.15960/j.cnki.issn.1007-6093.2019.02.010

运筹学学报 ›› 2019, Vol. 23 ›› Issue (2): 104-112.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.010

最大匹配的路变换图

刘岩^*, 雷梦霞, 黄晓娴

华南师范大学数学科学学院, 广州 510631

收稿日期:2017-07-14 出版日期:2019-06-15 发布日期:2019-06-15
通讯作者: 刘岩 E-mail:liuyan@scnu.edu.cn
基金资助:
国家自然科学基金（No.11551003），广州市科技计划项目（No.201510010265）

Path-transformation graph of maximum matchings

LIU Yan^*, LEI Mengxia, HUANG Xiaoxian

School of Mathematical Science, South China Normal University, Guangzhou 510631, China

Received:2017-07-14 Online:2019-06-15 Published:2019-06-15

摘要/Abstract

摘要： 图G的最大匹配的路变换图NM（G）是这样一个图，它以G的最大匹配为顶点，如果两个最大匹配M₁与M₂的对称差导出的图是一条路（长度没有限制），那么M₁和M₂在NM（G）中相邻.研究了这个变换图的连通性，分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

关键词: 最大匹配, 路变换图, 因子临界图, 有正赢量的二部图

Abstract: The path-transformation graph of maximum matchings of a graph G, denoted by NM(G), is a graph where vertices are maximum matchings of G and two maximum matchings M₁ and M₂ are adjacent in NM(G) if the symmetric difference of M₁ and M₂ induces a path (there is no limit for the length of the path). In the paper, we study the connectivity of the transformation graph, and obtain the necessary and sufficient condition that the transformation graph is a complete graph or a tree or a cycle, respectively.

Key words: maximum matching, path-transformation graph, factor-critical graph, bipartite graph with positive surplus

中图分类号:

O157.5

刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.

LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings[J]. Operations Research Transactions, 2019, 23(2): 104-112.

参考文献 15

[1]	Li X L. Transformation graphs[D]. Netherlands:The University of Twente, 1991.
[2]	Naddef D J, Pulleyblank W R. Hamiltonicity in (0, 1)-polyhedra[J]. Journal of Combinatorial Theory Series B, 1984, 37:41-52.
[3]	Zhang F J, Guo X F. Hamilton cycles in perfect matching graphs[J]. Journal of Xinjiang University, 1986, 4:10-16.
[4]	Zhang F J, Guo X F, Chen R S. Z-Transformation graphs of perfect matchings of hexagonal systems[J]. Discrete Mathematics, 1988, 72:405-415.
[5]	Zhang F J, Guo X F, Chen R. S. Connectivity of Z-transformation graphs of perfect matching of hexagonal systems[J]. Acta Mathematicae Applicatae Sinica, 1988, 4:131-135.
[6]	Wang S Y, Yuan J J, Liu Y, et al. On the maximum matching graph of a graph[J]. Operations Research Transactions, 1998, 2:13-17.
[7]	Eroh L, Schultz M. Matching graphs[J]. Journal of Graph Theory, 1998, 2:73-86.
[8]	Liu Y, Lin Y X, Huang Y Q, et al. The girth of the maximum matching graph[J]. OR Transactions, 2001, 5:13-20.
[9]	Liu Y. Characterizations of maximum matching graphs of certain types[J]. Discrete Mathematics, 2005, 290:283-289.
[10]	Liu Y, Yan G. Y. Graphs isomorphic to their maximum matching graphs[J]. Acta Mathematica Sinica, 2009, 25:1507-1516.
[11]	Liu Y, Wang S Y. The connectivity of maximum matching graph[J]. Journal of Systems Science and Complexity, 2004, 17:33-38.
[12]	Liu Y, Liu Z B. Second kind of maximum matching graph[J]. Discrete Mathematics, 2014, 323:27-34.
[13]	Lovasz L, Plummer M D. Matching Theory[M]. North Holland:Elsevier Science Publishers, 1985.
[14]	Bondy J A, Murty U S R. Graph Theory with Applications[M]. London:Macmillan Press Ltd, 1976.
[15]	Liu Y, Liu G Z. Number of maximum matchings of bipartite graph with positive surplus[J]. Discrete Mathematics, 2004, 274:311-318.

最大匹配的路变换图

Path-transformation graph of maximum matchings

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 15

相关文章 1

编辑推荐

Metrics

本文评价