Geodesic
Equimatchable bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 77-94 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A graph is called equimatchable if all of its maximal matchings have the same size. Lesk et al. [Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254] has provided a characterization of equimatchable bipartite graphs. Motivated by the fact that this characterization is not structural, Frendrup et al. [A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190] has also provided a structural characterization for equimatchable graphs with girth at least five, in particular, a characterization for equimatchable bipartite graphs with girth at least six. In this paper, we extend the characterization of Frendrup by eliminating the girth condition. For an equimatchable graph, an edge is said to be a critical-edge if the graph obtained by the removal of this edge is not equimatchable. An equimatchable graph is called edge-critical, denoted by ECE, if every edge is critical. Noting that each ECE-graph can be obtained from some equimatchable graph by recursively removing non-critical edges, each equimatchable graph can also be constructed from some ECE-graph by joining some non-adjacent vertices. Our study reduces the characterization of equimatchable bipartite graphs to the characterization of bipartite ECE-graphs.
Keywords: equimatchable, edge-critical, bipartite graphs 
@article{DMGT_2023_43_1_a4,
     author = {B\"uy\"uk\c{c}olak, Yasemin and G\"oz\"upek, Didem and \"Ozkan, Sibel},
     title = {Equimatchable bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {77--94},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a4/}
}
TY  - JOUR
AU  - Büyükçolak, Yasemin
AU  - Gözüpek, Didem
AU  - Özkan, Sibel
TI  - Equimatchable bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 77
EP  - 94
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a4/
LA  - en
ID  - DMGT_2023_43_1_a4
ER  - 
%0 Journal Article
%A Büyükçolak, Yasemin
%A Gözüpek, Didem
%A Özkan, Sibel
%T Equimatchable bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 77-94
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a4/
%G en
%F DMGT_2023_43_1_a4
Büyükçolak, Yasemin; Gözüpek, Didem; Özkan, Sibel. Equimatchable bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 77-94. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a4/

[1] S. Akbari, A.H. Ghodrati, M.A. Hosseinzadeh and A. Iranmanesh, Equimatchable regular graphs, J. Graph Theory 87 (2018) 35–45. https://doi.org/10.1002/jgt.22138

[2] M. Demange and T. Ekim, Efficient recognition of equimatchable graphs, Inform. Process. Lett. 114 (2014) 66–71. https://doi.org/10.1016/j.ipl.2013.08.002

[3] Z. Deniz and T. Ekim, Edge-stable equimatchable graphs, Discrete Appl. Math. 261 (2019) 136–147. https://doi.org/10.1016/j.dam.2018.09.033

[4] Z. Deniz, T. Ekim, T.R. Hartinger, M. Milanič and M. Shalom, On two extensions of equimatchable graphs, Discrete Optim. 26 (2017) 112–130. https://doi.org/10.1016/j.disopt.2017.08.002

[5] Z. Deniz and T. Ekim, Critical equimatchable graphs, preprint.

[6] A. Frendrup, B. Hartnell and P.D. Vestergaard, A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190.

[7] B. Grünbaum, Matchings in polytopal graphs, Networks 4 (1974) 175–190. https://doi.org/10.1002/net.3230040207

[8] P. Hall, On representatives of subsets, J. London Math. Soc. s1-10 (1935) 26–30. https://doi.org/10.1112/jlms/s1-10.37.26

[9] P.L. Hammer, U.N. Peled and X. Sun, Difference graphs, Discrete Appl. Math. 28 (1990) 35–44. https://doi.org/10.1016/0166-218X(90)90092-Q

[10] M. Lesk, M. Plummer and W.R. Pulleyblank, Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254.

[11] M. Lewin, Matching-perfect and cover-perfect graphs, Israel J. Math. 18 (1974) 345–347. https://doi.org/10.1007/BF02760842

[12] L. Lovász and M. Plummer, Matching Theory, Annals of Discrete Mathematics (North-Holland, Amsterdam, 1986).

[13] D.H.-C. Meng, Matchings and Coverings for Graphs (Michigan State University, East Lansing, MI, 1974).

[14] D.P. Sumner, Randomly matchable graphs, J. Graph Theory 3 (1979) 183–186. https://doi.org/10.1002/jgt.3190030209