The minimum degree of minimal $k$-factor-critical claw-free graphs*
| Autor: | Guo, Jing, Li, Qiuli, Lu, Fuliang, Zhang, Heping |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. Comment: 17 pages, 12 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|