Article in volume
Authors:
Yasemin Büyükçolak
Department of Mathematics, Gebze Technical University
email: turediyasemin@gmail.com
Didem Gözüpek
Department of Computer Engineering, Gebze Technical University
email: didem.gozupek@gtu.edu.tr
Title:
Equimatchable bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 77-94
Received: 2020-02-09 , Revised: 2020-07-21 , Accepted: 2020-07-21 , Available online: 2020-09-12 , https://doi.org/10.7151/dmgt.2356
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:
equimatchable, edge-critical, bipartite graphs
References:
- 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 - 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 - 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 - 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 - Z. Deniz and T. Ekim, Critical equimatchable graphs, preprint.
- A. Frendrup, B. Hartnell and P.D. Vestergaard, A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190.
- B. Grünbaum, Matchings in polytopal graphs, Networks 4 (1974) 175–190.
https://doi.org/10.1002/net.3230040207 - 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 - 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 - M. Lesk, M. Plummer and W.R. Pulleyblank, Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254.
- M. Lewin, Matching-perfect and cover-perfect graphs, Israel J. Math. 18 (1974) 345–347.
https://doi.org/10.1007/BF02760842 - L. Lovász and M. Plummer, Matching Theory, Annals of Discrete Mathematics (North-Holland, Amsterdam, 1986).
- D.H.-C. Meng, Matchings and Coverings for Graphs (Michigan State University, East Lansing, MI, 1974).
- D.P. Sumner, Randomly matchable graphs, J. Graph Theory 3 (1979) 183–186.
https://doi.org/10.1002/jgt.3190030209
Close