Equimatchable Regular Graphs. Issue 1 (8th March 2017)

• Record Type: Journal Article
• Authors: Akbari, Saieed; Ghodrati, Amir Hossein; Hosseinzadeh, Mohammad Ali; Iranmanesh, Ali
• Is Part Of: Journal of graph theory. Volume 87:Issue 1(2018)
• Page Start: 35
• Page End: 45
• Publication Date: 2017-03-08
• Subjects: equimatchable -- regular graph -- triangle‐free graph -- 2010 AMS Subject Classification Number: 05C70 -- 05C75; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22138
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K 4 and K 3, 3 . We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r ‐regular graph, then G ∈ { K r + 1, K r, r } . Also it is proved that for an even r, a connected triangle‐free equimatchable r ‐regular graph is isomorphic to one of the graphs C 5, C 7, and K r, r .