Without loss of generality, assume y = z Since ?(G(v 1 )) > k, there exist k + 1 internally disjoint x ? y paths P i , 1 ? i ? k + 1, in G(v 1 ) by Menger's Theorem. Note that at most one of them is a path of length 1. Let P k+1 be such a path if , k be integers such that 0 = k 0 < k 1 < · · · < k = k + 1. Similar to the proofs of Proposition 3.1, we can construct k i ? k i?1 + 1 internally disjoint S-trees T i,ji , 1 ? j i ? k i ? k i?1 + 1, in ( ki j=ki?1+1 P j ) T i for each i, where 1 ? i ? ? 1, and k ? k ?1 internally disjoint S-trees T ,j , 1 ? j i ? k ? k ?1 , in ( k j=k ?1 +1 P j ) T i . By Observation 3.1 and 3.2, T i,ji and T r,jr are internally disjoint for i = r. Thus T i,ji , 1 ? i ? , 1 ? j i ? k i ? k i?1 + 1 are k + internally disjoint S-trees. If all of x, y , z are the same vertex in G(v i ) Since ?(G(v 1 )) ? ?(G(v 1 )) > k, x has k neighbors, say x 1 , x 2 , . . . , x k , in G(v 1 )). Let P i be the path xx i , and let k 0 , k 1 , . . . , k be integers such that 0 = k 0 < k 1 < · · · < k = k. Similar to the proofs of Proposition 3.1, we can construct k i ? k i?1 + 1 internally disjoint S-trees T i,ji , 1 ? j i ? k i ? k i?1 + 1, in ( ki j=ki?1+1 P j ) T i for each i, where 1 ? i ? . By Observation 3.1 and 3.2, T i,ji and T r,jr are internally disjoint for i = r. Thus T i,ji , 1 ? i ? , 1 ? j i ? k i ? k i?1 + 1 are k + internally disjoint S-trees, ? i ? , 1 ? j i ? k i ? k i?1 + 1 are k + internally disjoint S-trees ,
Rainbow trees in graphs and generalized connectivity, Networks, vol.54, issue.4, pp.360-367, 2010. ,
DOI : 10.1002/net.20339
On connectivity of the Cartesian product of two graphs, Applied Mathematics and Computation, vol.102, issue.2-3, pp.129-137, 1999. ,
DOI : 10.1016/S0096-3003(98)10041-3
Product Graphs Structure and Recongnition, 2000. ,
On the edge-connectivity of Cartesian product graphs, Asian-Eur, J. Math, vol.1, pp.93-98, 2008. ,
The generalized connectivity of complete bipartite graphs, Ars Combin, vol.104, 2012. ,
Note on the hardness of generalized connectivity, Journal of Combinatorial Optimization, vol.54, issue.4 ,
DOI : 10.1007/s10878-011-9399-x
The tree connectivity of regular complete bipartite graphs, J. Combin. Math. Combin. Comput, vol.74, pp.279-293, 2010. ,
Graphs with given group and given graph-theoretical properties, Journal canadien de math??matiques, vol.9, issue.0, pp.515-525, 1957. ,
DOI : 10.4153/CJM-1957-060-7
Connectivity of Cartesian products of graphs, Applied Mathematics Letters, vol.21, issue.7, pp.682-685, 2008. ,
DOI : 10.1016/j.aml.2007.06.010
Algorithms for VLSI physical design automation, 1999. ,
Congruent Graphs and the Connectivity of Graphs, American Journal of Mathematics, vol.54, issue.1, pp.150-168, 1932. ,
DOI : 10.2307/2371086
Topics in Graph Theory. Graphs and Their Cartesian Product. A K Peters, 2008. ,
Connectivity of Cartesian product graphs, Discrete Mathematics, vol.306, issue.1, pp.159-165, 2006. ,
DOI : 10.1016/j.disc.2005.11.010