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} 美元,其中美元为正整数。考虑到非双边图,我们的定性意味着对无三角公平图表的线性时间识别算法。

0
下载
关闭预览

相关内容

【斯坦福Jiaxuan You】图学习在金融网络中的应用,24页ppt
专知会员服务
45+阅读 · 2021年9月19日
一份简单《图神经网络》教程,28页ppt
专知会员服务
127+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
AAAI2020 图相关论文集
图与推荐
11+阅读 · 2020年7月15日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
Arxiv
0+阅读 · 2021年10月18日
Arxiv
0+阅读 · 2021年10月15日
VIP会员
相关VIP内容
【斯坦福Jiaxuan You】图学习在金融网络中的应用,24页ppt
专知会员服务
45+阅读 · 2021年9月19日
一份简单《图神经网络》教程,28页ppt
专知会员服务
127+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
相关资讯
AAAI2020 图相关论文集
图与推荐
11+阅读 · 2020年7月15日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
Top
微信扫码咨询专知VIP会员