Distance Between Two Vertices of Maximum Matching Graphs
Distance Between Two Vertices of Maximum Matching Graphs
摘要
The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings which differ by exactly one edge. In this paper, we obtain a lower bound of distance between two vertices of maximum matching graph, and give a necessary and sufficient condition that the bound can be reached.
参考文献10
-
1Bondy, J.A., Murty, U.S.R. Graph theory with applications. Macmillan Press Ltd., London, 1976
-
2Eroh, L., Schultz, M. Matching graphs. J. Graph Theory, 2:73-86 (1998)
-
3Liu, Y., Lin, Y., Huang, Y., Wang, S. The girth of the maximum matching graph. OR Transactions, 5:13-20 (2001)
-
4Lovasz, L., Plummet, M.D. Matching Theory. Elsevier Science Publishers, B.V. North Holland, 1985
-
5Maurer, S.B. Matroid basis graphs Ⅰ. J. Comb. Theory B., 14:216-240 (1973)
-
6Maurer, S.B. Matroid basis graphs Ⅱ.d. Comb. Theory B., 15:121-145 (1973)
-
7Naddef, D.J., Pulleyblank, W.R. Hamiltonicity in (0, 1)-polyhedra. J. Comb. Theory B., 37:41-52 (1984)
-
8Wang, S.Y.et al. On the maximum matching-graph of a graph. OR Transactions, 2: 13-17 (1998) .
-
9Zhang, F.J., Guo, X.F. Hamilton cycles in perfect matching graphs. J. Xinjiang Univ., 4:10-16 (1986)
-
10Zhang, F., Guo, X., Chen, R. Z-Transformation graphs of perfect matchings of hexagonal systems. Disc.Math., 72:405-415 (1988)
-
1Yan LIU,Gui Ying YAN.Graphs Isomorphic to Their Maximum Matching Graphs[J].Acta Mathematica Sinica,English Series,2009,25(9):1507-1516. 被引量：4
-
2LIUYan,WANGShiying.THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS[J].Journal of Systems Science & Complexity,2004,17(1):33-38. 被引量：1
-
3QIAN Chao,YU Yang,ZHOU Zhi-Hua.Variable solution structure can be helpful in evolutionary optimization[J].Science China(Information Sciences),2015,58(11):141-157. 被引量：2
