The generalized 3-connectivity of star graphs and bubble-sort graphs

详细信息    查看全文

• 作者：Shasha Li^a ; ^{lss@nit.zju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Jianhua Tu ; ^b ; ^{tujh81@163.com" class="auth_mail" title="E-mail the corresponding author} ; Chenyan Yu^a ; ^{chenyan@hotmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Generalized 3-connectivity ; Internally disjoint trees ; Cayley graphs ; Star graphs ; Bubble-sort graphs
• 刊名：Applied Mathematics and Computation
• 出版年：2016
• 出版时间：1 February 2016
• 年：2016
• 卷：274
• 期：Complete
• 页码：41-46
• 全文大小：281 K

文摘

For S ⊆ G, let κ(S) denote the maximum number r   of edge-disjoint trees 4782&_mathId=si1.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=11be656dc2a0b3097ed20b73cc594ac2" title="Click to view the MathML source">T₁,T₂,…,T_r$T_1,T_2,\dots ,T_r$ in G   such that 4782&_mathId=si2.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=97099ac10ecfb705f4b180998903982d" title="Click to view the MathML source">V(T_i)∩V(T_j)=S$V\left(T_i\right)\cap V\left(T_j\right)=S$ for any 4782&_mathId=si3.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=3a30cbd364cb86730aceae87dc03e4c7" title="Click to view the MathML source">i,j∈{1,2,⋯,r}$i,j\in \{1,2,\cdots ,r\}$ and i ≠ j. For every 2 ≤ k ≤ n, the generalized k-connectivity of G κ_k(G) is defined as the minimum κ(S) over all k-subsets S   of vertices, i.e., 4782&_mathId=si4.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=7d9586e9814bc64773ae667847c6eaa3" title="Click to view the MathML source">κ_k(G)=${\kappa }_k\left(G\right)=$ min 4782&_mathId=si5.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=8317c9ee7dd67160b2ee2a0a35ff06aa">4782-si5.gif">$\left\{\kappa \right(S\left)\right|S\subseteq V\left(G\right)and\left|S\right|=k\}$. Clearly, κ₂(G) corresponds to the traditional connectivity of G. The generalized k-connectivity can serve for measuring the capability of a network G to connect any k vertices in G. Cayley graphs have been used extensively to design interconnection networks. In this paper, we restrict our attention to two classes of Cayley graphs, the star graphs S_n and the bubble-sort graphs B_n, and investigate the generalized 3-connectivity of S_n and B_n  . We show that 4782&_mathId=si6.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=6a6ff45dd55448204945ab2844634644" title="Click to view the MathML source">κ₃(S_n)=n−2${\kappa }_3\left(S_n\right)=n-2$ and 4782&_mathId=si7.gif&_user=111111111&_pii=S0096300315014782&_rdoc=1&_issn=00963003&md5=f0d4f209fc02b22d464d2654f74655b5" title="Click to view the MathML source">κ₃(B_n)=n−2${\kappa }_3\left(B_n\right)=n-2$.