Sparse graphs with an independent or foresty minimum vertex cut
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929616792322048 |
|---|---|
| author | Cheng, Kun Tang, Yurui Zhan, Xingzhi |
| author_facet | Cheng, Kun Tang, Yurui Zhan, Xingzhi |
| contents | A connected graph is called fragile if it contains an independent vertex cut. In 2002 Chen and Yu proved that every connected graph of order $n$ and size at most $2n-4$ is fragile, and in 2013 Le and Pfender characterized the non-fragile graphs of order $n$ and size $2n-3.$ It is natural to consider minimum vertex cuts. We prove two results. (1) Every connected graph of order $n$ with $n\ge 7$ and size at most $\lfloor 3n/2\rfloor$ has an independent minimum vertex cut; (2) every connected graph of order $n$ with $n\ge 7$ and size at most $2n$ has a foresty minimum vertex cut. Both results are best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03869 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse graphs with an independent or foresty minimum vertex cut Cheng, Kun Tang, Yurui Zhan, Xingzhi Combinatorics 05C35, 05C40, 05C69 A connected graph is called fragile if it contains an independent vertex cut. In 2002 Chen and Yu proved that every connected graph of order $n$ and size at most $2n-4$ is fragile, and in 2013 Le and Pfender characterized the non-fragile graphs of order $n$ and size $2n-3.$ It is natural to consider minimum vertex cuts. We prove two results. (1) Every connected graph of order $n$ with $n\ge 7$ and size at most $\lfloor 3n/2\rfloor$ has an independent minimum vertex cut; (2) every connected graph of order $n$ with $n\ge 7$ and size at most $2n$ has a foresty minimum vertex cut. Both results are best possible. |
| title | Sparse graphs with an independent or foresty minimum vertex cut |
| topic | Combinatorics 05C35, 05C40, 05C69 |
| url | https://arxiv.org/abs/2412.03869 |