On Generalized 3-Connectivity of the Strong Product of Graphs

Abstract

Let G be a connected graph with n vertices and let k be an integer such that 2 k n. The generalized connectivity k(G) of G is the greatest positive integer ` for which G contains at least ` internally disjoint trees connecting S for any set S V (G) of k vertices. We focus on the generalized connectivity of the strong product G1 G2 of connected graphs G1 and G2 with at least three vertices and girth at least ve, and we prove the sharp bound 3(G1 G2) 3(G1) 3(G2) + 3(G1) + 3(G2) �� 1: