The generalized 3-connectivity of Lexicographic product graphs

Abstract

The generalized $k$-connectivity $\hat{I}{º}_k(G)$ of a graph $G$, introduced by Chartrand et al., is a natural and nice generalization of the concept of (vertex-)connectivity. In this paper, we prove that for any two connected graphs $G$ and $H$, $\hat{I}{º}_3(G\circ H)\ge \hat{I}{º}_3(G)|V(H)|$. We also give upper bounds for $\hat{I}{º}_3(G\square H)$ and $\hat{I}{º}_3(G\circ H)$. Moreover, all the bounds are sharp.

13 pages. arXiv admin note: text overlap with arXiv:1103.6095