Well-indumatched trees and graphs of bounded girth
Australasian Journal of Combinatorics, cilt.85, ss.61-81, 2023 (ESCI, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 85
- Basım Tarihi: 2023
- Dergi Adı: Australasian Journal of Combinatorics
- Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI), Scopus, MathSciNet, zbMATH, Directory of Open Access Journals
- Sayfa Sayıları: ss.61-81
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A graph G is called well-indumatched if all of its maximal induced match-ings have the same size. In this paper, we characterize all well-indumatch-ed trees. We provide a linear time algorithm to decide whether a tree is well-indumatched or not. Then, we characterize minimal well-indu-matched graphs of girth at least 9 and show subsequently that for an odd integer g ≥ 9 and g ≠ 11, there is no well-indumatched graph of girth g. On the other hand, there are infinitely many well-indumatched unicyclic graphs of girth k, where k ∈ {3, 5, 7} or k is an even integer greater than 2. We also show that, although the recognition of well-indumatched graphs is known to be co-NP-complete in general, one can recognize in polynomial time well-indumatched graphs, where the size of maximal induced matchings is fixed.