论文标题
图形的顶点切割和邻里复合物的连通性
Vertex cut of a graph and connectivity of its neighbourhood complex
论文作者
论文摘要
我们表明，如果图$ g $满足某些条件，那么社区复杂$ \ Mathcal {n}（g）$的连接严格小于$ g $的顶点连接。作为应用程序，我们提供了邻域复合物的连接性与刚性脉络图的顶点连接性之间的关系，以及满足某些属性的弱三角图。此外，我们证明，对于图$ g $，如果存在一个顶点$ v $满足$ v $的任何$ k $ -subset $ s $ s $的属性，则存在一个顶点$ v_s \ neq v $ $ v $ $ s $，因此，$ s $是$ v_s $，$ v_s $，然后是$ \ nathcal is $ v_s $ is的子集，然后$（k-1）$ - 连接意味着$ \ Mathcal {n}（g）$是$（k-1）$ - 连接。因此，我们表明：（i）Queen和King图的邻域复合物是仅连接的，并且（ii）如果$ g $是$（n+1）$ - 连接的弦图，它不会折叠到大小$ n+2 $的集团，则是$ \ nathcal {n}（n}（g）$ n $ n $ connected。
We show that if a graph $G$ satisfies certain conditions then the connectivity of neighbourhood complex $\mathcal{N}(G)$ is strictly less than the vertex connectivity of $G$. 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 $G$ if there exists a vertex $v$ satisfying the property that for any $k$-subset $S$ of neighbours of $v$, there exists a vertex $v_S \neq v$ such that $S$ is subset of neighbours of $v_S$, then $\mathcal{N}(G-\{v\})$ is $(k-1)$-connected implies that $\mathcal{N}(G)$ is $(k-1)$-connected. As a consequence of this, we show that:(i) neighbourhood complexes of queen and king graphs are simply connected and (ii) if $G$ is a $(n+1)$-connected chordal graph which is not folded onto a clique of size $n+2$, then $\mathcal{N}(G)$ is $n$-connected.
