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
专知会员服务
43+阅读 · 2021年9月19日
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
图表示学习Graph Embedding综述
图与推荐
10+阅读 · 2020年3月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
已删除
将门创投
3+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Facebook PyText 在 Github 上开源了
AINLP
7+阅读 · 2018年12月14日
【关关的刷题日记60】Leetcode 437. Path Sum III
Arxiv
0+阅读 · 2021年10月22日
Arxiv
0+阅读 · 2021年10月21日
Arxiv
1+阅读 · 2021年10月20日
Arxiv
0+阅读 · 2021年10月18日
Arxiv
0+阅读 · 2021年10月15日
Arxiv
0+阅读 · 2021年10月15日
VIP会员
相关VIP内容
【斯坦福Jiaxuan You】图学习在金融网络中的应用,24页ppt
专知会员服务
43+阅读 · 2021年9月19日
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
图表示学习Graph Embedding综述
图与推荐
10+阅读 · 2020年3月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
已删除
将门创投
3+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Facebook PyText 在 Github 上开源了
AINLP
7+阅读 · 2018年12月14日
【关关的刷题日记60】Leetcode 437. Path Sum III
相关论文
Arxiv
0+阅读 · 2021年10月22日
Arxiv
0+阅读 · 2021年10月21日
Arxiv
1+阅读 · 2021年10月20日
Arxiv
0+阅读 · 2021年10月18日
Arxiv
0+阅读 · 2021年10月15日
Arxiv
0+阅读 · 2021年10月15日
Top
微信扫码咨询专知VIP会员