1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Equimatchable Bipartite Graphs

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 09 Feb 2020
Accepted: 21 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

MSC 2010

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

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

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

[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. doi:10.1016/j.disopt.2017.08.00210.1016/j.disopt.2017.08.002Search in Google Scholar

[5] Z. Deniz and T. Ekim, Critical equimatchable graphs, preprint.Search in Google Scholar

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

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

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

[9] P.L. Hammer, U.N. Peled and X. Sun, Difference graphs, Discrete Appl. Math. 28 (1990) 35–44. doi:10.1016/0166-218X(90)90092-Q10.1016/0166-218X(90)90092-QSearch in Google Scholar

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

[11] M. Lewin, Matching-perfect and cover-perfect graphs, Israel J. Math. 18 (1974) 345–347. doi:10.1007/BF0276084210.1007/BF02760842Search in Google Scholar

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

[13] D.H.-C. Meng, Matchings and coverings for graphs (Michigan State University, East Lansing, MI, 1974).Search in Google Scholar

[14] D.P. Sumner, Randomly matchable graphs, J. Graph Theory 3 (1979) 183–186. doi:10.1002/jgt.319003020910.1002/jgt.3190030209Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo