Cubic vertices of minimal bicritical graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909346980429824 |
|---|---|
| author | Guo, Jing Wu, Hailun Zhang, Heping |
| author_facet | Guo, Jing Wu, Hailun Zhang, Heping |
| contents | A graph $G$ with four or more vertices is called bicritical if the removal of any pair of distinct vertices of $G$ results in a graph with a perfect matching. A bicritical graph is minimal if the deletion of each edge results in a non-bicritical graph. Recently, Y. Zhang et al. and F. Lin et al. respectively showed that bicritical graphs without removable edges and minimal bricks have at least four cubic vertices. In this note, we show that minimal bicritical graphs also have at least four cubic vertices, so confirming O. Favaron and M. Shi's conjecture in the case of $k=2$ on minimal $k$-factor critical graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_06503 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cubic vertices of minimal bicritical graphs Guo, Jing Wu, Hailun Zhang, Heping Combinatorics 05C70, 05C07 A graph $G$ with four or more vertices is called bicritical if the removal of any pair of distinct vertices of $G$ results in a graph with a perfect matching. A bicritical graph is minimal if the deletion of each edge results in a non-bicritical graph. Recently, Y. Zhang et al. and F. Lin et al. respectively showed that bicritical graphs without removable edges and minimal bricks have at least four cubic vertices. In this note, we show that minimal bicritical graphs also have at least four cubic vertices, so confirming O. Favaron and M. Shi's conjecture in the case of $k=2$ on minimal $k$-factor critical graphs. |
| title | Cubic vertices of minimal bicritical graphs |
| topic | Combinatorics 05C70, 05C07 |
| url | https://arxiv.org/abs/2305.06503 |