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 条

[31] Matching algorithms are fast in sparse random graphs
Bast, H
Mehlhorn, K
Schäfer, G
Tamaki, H
THEORY OF COMPUTING SYSTEMS, 2006, 39 (01) : 3 - 14
[32] A characterization of nonfeasible sets in matching covered graphs
Liu, Qinghai
Cui, Qing
Feng, Xing
Lu, Fuliang
JOURNAL OF GRAPH THEORY, 2020, 95 (04) : 509 - 526
[33] Bipartite subgraphs of graphs with maximum degree three
Bylka, SA
Idzik, A
Komar, J
GRAPHS AND COMBINATORICS, 1999, 15 (02) : 129 - 136
[34] Matching Algorithms Are Fast in Sparse Random Graphs
Holger Bast
Kurt Mehlhorn
Guido Schafer
Hisao Tamaki
Theory of Computing Systems, 2006, 39 : 3 - 14
[35] On Unicyclic Graphs with Uniquely Restricted Maximum Matchings
Vadim E. Levit
Eugen Mandrescu
Graphs and Combinatorics, 2013, 29 : 1867 - 1879
[36] THE MAXIMUM SPECTRAL RADIUS OF GRAPHS WITH A LARGE CORE
He, Xiaocong
Feng, Lihua
Stevanovic, Dragan
ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2023, 39 : 78 - 89
[37] The maximum spectral radius of irregular bipartite graphs
Xue, Jie
Liu, Ruifang
Guo, Jiaxin
Shu, Jinlong
ADVANCES IN APPLIED MATHEMATICS, 2023, 142
[38] Maximum Biplex Search over Bipartite Graphs
Luo, Wensheng
Li, Kenli
Zhou, Xu
Gao, Yunjun
Li, Keqin
2022 IEEE 38TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2022), 2022, : 898 - 910
[39] On Unicyclic Graphs with Uniquely Restricted Maximum Matchings
Levit, Vadim E.
Mandrescu, Eugen
GRAPHS AND COMBINATORICS, 2013, 29 (06) : 1867 - 1879
[40] Maximum nullity and zero forcing of circulant graphs
Linh Duong
Kroschel, Brenda K.
Riddell, Michael
Vander Meulen, Kevin N.
Van Tuyl, Adam
SPECIAL MATRICES, 2020, 8 (01): : 221 - 234

← 1 2 3 4 5 →