Search

Given a connected graph G and S ⊆ V (G) with | S | ≥ 2 , an S -tree is a such subgraph T = (V ′ , E ′) of G that is a tree with S ⊆ V ′ . Two S -trees T and T ′ are edge-disjoint if E (T) ∩ E (T ′) = ∅. Let λ G (S) be the maximum size of a set of edge-disjoint S -trees in G. The λ k -connectivity of G is defined as λ k (G) = min { λ G (S) : S ⊆ V (G) , | S | = k }. In this paper, we first show some structural properties of edge-disjoint S -trees by Fan Lemma and König-ore Formula. Then, the λ 4 -connectivity of the Cartesian product of trees is determined. That is, let T n 1 , T n 2 , ... , T n k be trees, then λ 4 (T n 1 □ T n 1 ⋯ □ T n k ) = k if | V (T n i ) | ≥ 4 for each i ∈ { 1 , 2 , ... , k } , otherwise λ 4 (T n 1 □ T n 2 □ ⋯ □ T n k ) = k − 1. As corollaries, λ 4 -connectivity for some graph classes such as hypercubes and meshes can be obtained directly. [ABSTRACT FROM AUTHOR]