中文

Operations Research Transactions >

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

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

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

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

Cite this article

LIU Yan, LEI Mengxia, HUANG Xiaoxian . Path-transformation graph of maximum matchings[J]. Operations Research Transactions, 2019 , 23(2) : 104 -112 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.010

References

[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
Outlines

/

〈 〉