We show that if a graph satisfies certain conditions then the connectivity of neighbourhood complex is strictly less than the vertex connectivity of . As an application, we give a relation between the connectivity of the neighbourhood complex and the vertex connectivity for stiff chordal graphs, and for weakly triangulated graphs satisfying certain properties. Further, we prove that for a graph if there exists a vertex satisfying the property that for any -subset of neighbours of , there exists a vertex such that is subset of neighbours of , then is -connected implies that is -connected. As a consequence of this, we show that:(i) neighbourhood complexes of queen and king graphs are simply connected and (ii) if is a -connected chordal graph which is not folded onto a clique of size , then is -connected.

生成讲解博客的中文版本

生成AI智能校验的中文版本