Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.15552 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911150667464704 |
|---|---|
| author | Zhao, Xiao Zheng, Haojie Dong, Fengming Li, Hengzhe Ma, Yingbin |
| author_facet | Zhao, Xiao Zheng, Haojie Dong, Fengming Li, Hengzhe Ma, Yingbin |
| contents | A graph is called equimatchable if all of its maximal matchings have the same size. Due to Eiben and Kotrbčík,, any connected graph with odd order and independence number $α(G)$ at most $2$ is equimatchable. Akbari et al. showed that for any odd number $r$, a connected equimatchable $r$-regular graph must be either the complete graph $K_{r+1}$ or the complete bipartite graph $K_{r,r}$. They also determined all connected equimatchable $4$-regular graphs and proved that for any even $r$, any connected equimatchable $r$-regular graph is either $K_{r,r}$ or factor-critical. In this paper, we confirm that for any even $r\ge 6$, there exists a unique connected equimatchable $r$-regular graph $G$ with $α(G)\geq 3$ and odd order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15552 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterization of Equimatchable Even-Regular Graphs Zhao, Xiao Zheng, Haojie Dong, Fengming Li, Hengzhe Ma, Yingbin Combinatorics 05C70, 05C75 A graph is called equimatchable if all of its maximal matchings have the same size. Due to Eiben and Kotrbčík,, any connected graph with odd order and independence number $α(G)$ at most $2$ is equimatchable. Akbari et al. showed that for any odd number $r$, a connected equimatchable $r$-regular graph must be either the complete graph $K_{r+1}$ or the complete bipartite graph $K_{r,r}$. They also determined all connected equimatchable $4$-regular graphs and proved that for any even $r$, any connected equimatchable $r$-regular graph is either $K_{r,r}$ or factor-critical. In this paper, we confirm that for any even $r\ge 6$, there exists a unique connected equimatchable $r$-regular graph $G$ with $α(G)\geq 3$ and odd order. |
| title | Characterization of Equimatchable Even-Regular Graphs |
| topic | Combinatorics 05C70, 05C75 |
| url | https://arxiv.org/abs/2408.15552 |