Vertex cut of a graph and connectivity of its neighbourhood complex

DOI10.1016/J.DISC.2023.113432MaRDI QIDQ6041558zbMATH OpenOpenAlexFDO

Authors Rekha Santhanam, Samir Shukla

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.03527

zbMATH Keywords

chordal graphsneighbourhood complexvertex connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Homotopy equivalences in algebraic topology (55P10)

Abstract: We show that if a graph $G$ satisfies certain conditions then the connectivity of neighbourhood complex $mathcalN(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}eqv$ such that $S$ is subset of neighbours of $v_S$, then $mathcalN(G-v)$ is $(k-1)$-connected implies that $mathcalN(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 $mathcalN(G)$ is $n$-connected.

Recommendations

• scientific article; zbMATH DE number 1796983
• On minimal neighbourhood-connected graphs
• Dominance complexes and vertex cover numbers of graphs
• scientific article; zbMATH DE number 13159
• scientific article; zbMATH DE number 409491

Cites work

• Circular chromatic numbers of Mycielski's graphs
• Combinatorial algebraic topology
• Complexes of graph homomorphisms
• Graph theory
• Homotopy types of box complexes
• Homotopy types of box complexes of chordal graphs
• scientific article; zbMATH DE number 5704224 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Weakly triangulated graphs

Cited in

(1)

• scientific article; zbMATH DE number 5161490 (Why is no real title available?)

This page was built for publication: Vertex cut of a graph and connectivity of its neighbourhood complex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041558)