The generalized 4-connectivity of exchanged hypercubes

摘要

Let S ⊆ V(G) and κG(S) denote the maximum number k of edge-disjoint trees T1,T2,…,Tk in G such that V(Ti)⋂V(Tj)=S for any i,j∈{1,2,…,k} and i ≠ j. For an integer r with 2 ≤ r ≤ n, the generalized r-connectivity of a graph G is defined as κr(G)=min{κG(S)|S⊆V(G) and |S|=r}. The parameter is a generalization of traditional connectivity. So far, almost all known results of κr(G) are about regular graphs and r=3. In this paper, we focus on κr(EH(s, t)) of the exchanged hypercube for r=4, where the exchanged hypercube EH(s, t) is not regular if s ≠ t. We show that κ4(EH(s,t))=min{s,t} for min{s, t} ≥ 3. As a corollary, we obtain that κ3(EH(s,t))=min{s,t} for min{s, t} ≥ 3.