Equimatchable claw-free graphs

TitleEquimatchable claw-free graphs
Publication TypeJournal Article
Year of Publication2018
AuthorsAkbari, S., H. Alizadeh, T. Ekim, D. Gözüpek, and M. Shalom
JournalDiscrete Mathematics
Volume341
Pagination2859-2871
ISSN0012-365X
KeywordsConnectivity, Equimatchable graph, Factor-critical
Abstract

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.

URLhttps://www.sciencedirect.com/science/article/pii/S0012365X18302140
DOI10.1016/j.disc.2018.06.043