Graphs isomorphic to their maximum matching graphs

被引：2

作者：

Liu, Yan ^{[1
]}

Yan, Gui Ying ^{[2
]}

机构：

[1] S China Normal Univ, Sch Math, Guangzhou 510631, Guangdong, Peoples R China

[2] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2009年 / 25卷 / 09期

关键词：

isomorphic; maximum matching graph; bipartite graph; factor-critical graph; PERFECT MATCHINGS; ENUMERATION;

D O I：

10.1007/s10114-009-7676-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The maximum matching graph a"(3)(G) of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in a"(3)(G) if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.

引用

页码：1507 / 1516

页数：10

共 50 条

[41] The isomorphic factorization of complete tripartite graphs K(m, n, s) into 9 x 2(k) isomorphic factors
Duan, Huiming
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2015, 18 (04) : 371 - 383
[42] On nonfeasible edge sets in matching-covered graphs
Zhao, Xiao
Dong, Fengming
Chen, Sheng
JOURNAL OF GRAPH THEORY, 2020, 95 (02) : 192 - 208
[43] A matching-minor monotone parameter for bipartite graphs
Arav, Marina
Deaett, Louis
Hall, H. Tracy
van der Holst, Hein
Young, Derek
LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 680 : 254 - 273
[44] ON TWO UNSOLVED PROBLEMS CONCERNING MATCHING COVERED GRAPHS
Lucchesi, Claudio L.
De Carvalho, Marcelo H.
Kothari, Nishad
Murty, U. S. R.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 1478 - 1504
[45] Fractional matching preclusion of the restricted HL-graphs
Zhang, Shunzhe
Liu, Huiqing
Li, Dong
Hu, Xiaolan
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (04) : 1143 - 1154
[46] A PARAMETRIC MAXIMUM FLOW ALGORITHM FOR BIPARTITE GRAPHS WITH APPLICATIONS
CHEN, YL
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 80 (01) : 226 - 235
[47] CONDITIONAL MATCHING PRECLUSION FOR (n, k)-STAR GRAPHS
Cheng, Eddie
Liptak, Laszlo
PARALLEL PROCESSING LETTERS, 2013, 23 (01)
[48] Maximum order of trees and bipartite graphs with a given rank
Ghorbani, E.
Mohammadian, A.
Tayfeh-Rezaie, B.
DISCRETE MATHEMATICS, 2012, 312 (24) : 3498 - 3501
[49] Approximating maximum uniquely restricted matchings in bipartite graphs
Baste, Julien
Rautenbach, Dieter
Sau, Ignasi
DISCRETE APPLIED MATHEMATICS, 2019, 267 : 30 - 40
[50] Distance-restricted matching extendability of fullerene graphs
Furuya, Michitaka
Takatou, Masanori
Tsuchiya, Shoichi
JOURNAL OF MATHEMATICAL CHEMISTRY, 2018, 56 (02) : 606 - 617

← 1 2 3 4 5 →