Vertex connectivity of chordal graphs

Abstract

Let $G$ be a finite graph and $\hat{I}º(G)$ the vertex connectivity of $G$. A chordal graph $G$ is called chordal${}^{\ast }$ 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${}^{\ast }$ graph $G$ on $n$ vertices satisfies $\hat{I}º(G)\le (n-1)-\lceil 2\sqrt{n}-2\rceil$. Furthermore, given an integer $0\le \hat{I}º\le (n-1)-\lceil 2\sqrt{n}-2\rceil$, a chordal${}^{\ast }$ graph $G$ on $n$ vertices satisfying $\hat{I}º(G)=\hat{I}º$ is constructed.

4 pages, 1 figure