A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et al. [8] provided a characterization of equimatchable graphs with girth at least $5$. In this paper, we extend this result by providing a complete structural characterization of equimatchable graphs with girth at least $4$, i.e., equimatchable graphs with no triangle, by identifying the equimatchable triangle-free graph families. Our characterization also extends the result given by Akbari et al. in [1], which proves that the only connected triangle-free equimatchable $r$-regular graphs are $C_5$, $C_7$ and $K_{r,r}$, where $r$ is a positive integer. Given a non-bipartite graph, our characterization implies a linear time recognition algorithm for triangle-free equimatchable graphs.
翻译:如果一个图表的所有最大匹配都具有相同的大小,则该图被称为“相等”。 Frendrup 等人 [8] 提供了以 Girth 至少 $5 美元表示的相等图形的定性。在本文中,我们扩展了这一结果,对以 Girth 至少 $4 美元表示的相等图形的完整结构定性,即没有三角形的相等图形。我们定性还扩展了Akbari 等人在 [1] 中提供的结果,该结果证明,唯一连通的无三角公平美元普通图形是 C_5美元、 C_7美元和 $K{r} 美元,其中美元为正整数。考虑到非双边图,我们的定性意味着对无三角公平图表的线性时间识别算法。