A note on removable edges in near-bricks
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_ | 1866914901655552000 |
|---|---|
| author | Wu, Deyu Zhang, Yipei Wang, Xiumei |
| author_facet | Wu, Deyu Zhang, Yipei Wang, Xiumei |
| contents | An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at least $Δ-2$ removable edges, where $Δ$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_09491 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A note on removable edges in near-bricks Wu, Deyu Zhang, Yipei Wang, Xiumei Combinatorics An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at least $Δ-2$ removable edges, where $Δ$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more. |
| title | A note on removable edges in near-bricks |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.09491 |