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!
|
Table of 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.