English

运筹学学报 >

2019 , Vol. 23 >Issue 2: 104 - 112

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.02.010

运筹学

最大匹配的路变换图

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

收稿日期: 2017-07-14

  网络出版日期: 2019-06-15

基金资助

国家自然科学基金（No.11551003），广州市科技计划项目（No.201510010265）

收起

Path-transformation graph of maximum matchings

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

Received date: 2017-07-14

  Online published: 2019-06-15

Fold

摘要

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

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

本文引用格式

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

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 M1 and M2 are adjacent in NM(G) if the symmetric difference of M1 and M2 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

参考文献

[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.
Options
文章导航

/

〈 〉