The minimum degree of minimal $k$-factor-critical claw-free graphs*
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913628197748736 |
|---|---|
| author | Guo, Jing Li, Qiuli Lu, Fuliang Zhang, Heping |
| author_facet | Guo, Jing Li, Qiuli Lu, Fuliang Zhang, Heping |
| contents | A graph $G$ of order $n$ is said to be $k$-factor-critical for integers $1\leq k< n$, if the removal of any $k$ vertices results in a graph with a perfect matching. A $k$-factor-critical graph is minimal if for every edge, the deletion of it results in a graph that is not $k$-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal $k$-factor-critical graph has minimum degree $k+1$. In this paper, we confirm the conjecture for minimal $k$-factor-critical claw-free graphs. Moreover, we show that every minimal $k$-factor-critical claw-free graph $G$ has at least $\frac{k-1}{2k}|V(G)|$ vertices of degree $k+1$ in the case of $(k+1)$-connected, yielding further evidence for S. Norine and R. Thomas' conjecture on the minimum degree of minimal bricks when $k=2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15821 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The minimum degree of minimal $k$-factor-critical claw-free graphs* Guo, Jing Li, Qiuli Lu, Fuliang Zhang, Heping Combinatorics 05C70, 05C07 F.2.2 A graph $G$ of order $n$ is said to be $k$-factor-critical for integers $1\leq k< n$, if the removal of any $k$ vertices results in a graph with a perfect matching. A $k$-factor-critical graph is minimal if for every edge, the deletion of it results in a graph that is not $k$-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal $k$-factor-critical graph has minimum degree $k+1$. In this paper, we confirm the conjecture for minimal $k$-factor-critical claw-free graphs. Moreover, we show that every minimal $k$-factor-critical claw-free graph $G$ has at least $\frac{k-1}{2k}|V(G)|$ vertices of degree $k+1$ in the case of $(k+1)$-connected, yielding further evidence for S. Norine and R. Thomas' conjecture on the minimum degree of minimal bricks when $k=2$. |
| title | The minimum degree of minimal $k$-factor-critical claw-free graphs* |
| topic | Combinatorics 05C70, 05C07 F.2.2 |
| url | https://arxiv.org/abs/2311.15821 |