Equimatchable claw-free graphs

Creative Commons License

Akbari S., Alizadeh H., EKİM T., Gözüpek D., Shalom M.

Discrete Mathematics, cilt.341, sa.10, ss.2859-2871, 2018 (SCI-Expanded, Scopus)

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 341 Sayı: 10
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1016/j.disc.2018.06.043
  • Dergi Adı: Discrete Mathematics
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2859-2871
  • Anahtar Kelimeler: Connectivity, Equimatchable graph, Factor-critical
  • Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm.