Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.07320 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913686088581120 |
|---|---|
| author | Hà, Tài Huy Hibi, Takayuki |
| author_facet | Hà, Tài Huy Hibi, Takayuki |
| contents | Let $G$ be a finite graph and $κ(G)$ the vertex connectivity of $G$. A chordal graph $G$ is called chordal$^*$ if no vertex of $G$ is adjacent to all other vertices of $G$. Using the syzygy theory in commutative algebra, it is proved that every chordal$^*$ graph $G$ on $n$ vertices satisfies $κ(G) \leq (n - 1) - \lceil2\sqrt{n}-2\,\rceil$. Furthermore, given an integer $0 \leq κ\leq (n - 1) - \lceil2\sqrt{n}-2\,\rceil$, a chordal$^*$ graph $G$ on $n$ vertices satisfying $κ(G) = κ$ is constructed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07320 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vertex connectivity of chordal graphs Hà, Tài Huy Hibi, Takayuki Combinatorics 05C40, 13D02 Let $G$ be a finite graph and $κ(G)$ the vertex connectivity of $G$. A chordal graph $G$ is called chordal$^*$ if no vertex of $G$ is adjacent to all other vertices of $G$. Using the syzygy theory in commutative algebra, it is proved that every chordal$^*$ graph $G$ on $n$ vertices satisfies $κ(G) \leq (n - 1) - \lceil2\sqrt{n}-2\,\rceil$. Furthermore, given an integer $0 \leq κ\leq (n - 1) - \lceil2\sqrt{n}-2\,\rceil$, a chordal$^*$ graph $G$ on $n$ vertices satisfying $κ(G) = κ$ is constructed. |
| title | Vertex connectivity of chordal graphs |
| topic | Combinatorics 05C40, 13D02 |
| url | https://arxiv.org/abs/2502.07320 |