The generalized 3-connectivity of graph products

摘要

The generalized k-connectivity κk(G) of a graph G, which was introduced by Chartrand et al. (1984), is a generalization of the concept of vertex connectivity. For this generalization, the generalized 2-connectivity κ2(G) of a graph G is exactly the connectivity κ(G) of G. In this paper, let G be a connected graph of order n and let H be a 2-connected graph. For Cartesian product, we show that κ3(G□H)≥κ3(G)+1 if κ(G)=κ3(G); κ3(G□H)≥κ3(G)+2 if κ(G) > κ3(G). Moreover, above bounds are sharp. As an example, we show that κ3(Cn1□Cn2□⋯Cnk︷k)=2k−1, where Cni is a cycle. For lexicographic product, we prove that κ3(H∘G)≥max{3δ(G)+1,⌈3n+12⌉} if δ(G)<2n−13, and κ3(H∘G)=2n if δ(G)≥2n−13.