The λ4-Connectivity of the Cartesian Product of Trees

Given a connected graph G and S subset of V (G) with vertical bar S vertical bar >= 2, an S-tree is a such subgraph T = (V 0;E0) of G that is a tree with S subset of V 0. Two S-trees T and T 0 are edge-disjoint if E (T) boolean AND E(T' = empty set). Let lambda(G)(S) be the maximum size of a set of edge-disjoint S-trees in G. The lambda(k)-connectivity of G is defined as lambda(k)(G) = minf{lambda(G)(S) : S subset of V (G); vertical bar S vertical bar = k}. In this paper, we first show some structural properties of edge-disjoint S-trees by Fan Lemma and Konig-ore Formula. Then, the lambda -connectivity of the Cartesian product of trees is determined. That is, let T-n1; T-n2 ...,T-nk be trees, then lambda(4)(T-n1 square T-n1 center dot center dot center dot square 2T(nk)) = k if vertical bar V (T-ni)vertical bar >= 4 for each i is an element of {1, 2, ...,k}, otherwise lambda(4) (T-n1 square T-n2 square 2T(nk)) = k - 1. As corollaries, lambda(4)-connectivity for some graph classes such as hypercubes and meshes can be obtained directly.