The generalized 3-connectivity of Cartesian product
Hengzhe Li, Xueliang Li, Yuefang Sun
Abstract
The generalized connectivity of a graph, which was introduced by
Chartrand et al. in 1984, is a generalization of the concept of vertex
connectivity. Let S be a nonempty set of vertices of
G, a collection
{T1,T2,…,Tr}
of trees in G is said to be internally disjoint trees
connecting S if E(Ti)∩
E(Tj)=∅ and
V(Ti)∩V(Tj)=S for any pair of
distinct integers i,j, where
1≤i,j≤r. For an integer k
with 2≤k≤n, the k-connectivity
κk(G) of G is the greatest
positive integer r for which G contains at
least r internally disjoint trees connecting
S for any set S of k vertices
of G. Obviously,
κ2(G)=κ(G) is the connectivity of
G. Sabidussi's Theorem showed that
κ(G ☐ H) ≥κ(G)+κ(H) for
any two connected graphs G and H. In this
paper, we prove that for any two connected graphs G and
H with
κ3(G)≥κ3(H), if
κ(G)>κ3(G), then
κ3(G ☐ H)≥
κ3(G)+κ3(H); if
κ(G)=κ3(G), then
κ3(G ☐ H)≥κ3(G)+κ3(H)-1.
Our result could be seen as an extension of Sabidussi's Theorem.
Moreover, all the bounds are sharp.
Full Text: PDF PostScript