最大匹配的路变换图

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

Abstract

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

CLC Number:

O157.5

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

References 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

Knowledge

Abstract

Cite this article

share this article

References 15

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	LAN Yongxin, SHI Yongtang, SONG Zixia. Planar Turán number and planar anti-Ramsey number of graphs [J]. Operations Research Transactions, 2021, 25(3): 200-216.
[2]	WANG Yajing, GAO Yubin. Cacti with larger Randić index [J]. Operations Research Transactions, 2020, 24(4): 135-144.
[3]	CHEN Hongling, WANG Huijuan, SUN Fengyan, XUE Juan, GAO Hongwei. Linear arboricity of planar graphs with maximum degree at least seven [J]. Operations Research Transactions, 2020, 24(3): 154-160.
[4]	CHEN Tao. Upper bounds on minimum balanced bipartition of Hamilton plane graphs [J]. Operations Research Transactions, 2020, 24(3): 161-166.
[5]	TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths [J]. Operations Research Transactions, 2020, 24(1): 140-146.
[6]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[7]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[8]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[9]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[10]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[11]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[12]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[13]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[14]	MEI Ruoxing, WANG Ligong, WANG Luhua, WANG Zhanqing. Laplacian spectral characterizations of unicyclic graphs H( p, t K_{ 1, m}) [J]. Operations Research Transactions, 2015, 19(1): 57-64.
[15]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.