Two definitions of $k$-connectivity:

1) A topological space $X $is said to be $k$-connected if every map from a sphere $\mathbb{S}^{n} \to X$ extends to a map from the ball $\mathbb{B}^{n} \to X$ for $n = 0, 1, . . . , k$.

2) A graph $G$ is said to be $k$-connected (or $k$-vertex connected, or $k$-point connected) if there does not exist a set of $k-1$ vertices whose removal disconnects the graph. [1]

...are these ideas related? Consider for example a simplicial complex formed from the neighbourhoods of vertices of a graph (see Kahle 2007). Does $k$-connectivity of the complex imply $k$-vertex connectivity of the underlying graph?

My answer is that they are unrelated, since $k$-vertex connectivity of some vertices does not imply anything "in general" about the connectedness of a complex built on that space.

But an $n$-cycle for example is no more than 1-connected (remove any vertex and the graph disconnects), and it is also only path connected in a topological sense if we build a simplicial complex by gluing the 1-simplices of the cycle together to a form a space homeomorphic to a 1-sphere.

[1] These are the definitions from Mathew Kahle "The neighborhood complex of a random graph", J. Comb. Th. A. 114 (2007), and Wolfram Mathworld.



You must log in to answer this question.

Browse other questions tagged .