<p>Connectivity is a classical indicator to reflect the reliability of network. According to the distribution of fault processors, conditional connectivity of network has received wide attention. In this paper, we prove that every minimum 3-extra-cut set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(F\)</EquationSource> </InlineEquation> of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(r\)</EquationSource> </InlineEquation>-regular bipartite hierarchical graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> is isomorphic to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(N_G(C_4), N_G(P_4)\)</EquationSource> </InlineEquation> or <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(N_G(S_4)\)</EquationSource> </InlineEquation>, if for each subgraph <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(G_i\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(G_i-F_i\)</EquationSource> </InlineEquation> has no isolated vertices, and for a component <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(H\)</EquationSource> </InlineEquation> of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(G_1-F_1\)</EquationSource> </InlineEquation>, which is also a component of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(G-F\)</EquationSource> </InlineEquation>, satisfies <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(|N_{G_1}(H)| \geq \alpha - 4l - |H| + 4\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(|N_{G - G_1}(H)| \geq l|H|\)</EquationSource> </InlineEquation>. It follows that <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(3\)</EquationSource> </InlineEquation>-extra-connectivity <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\kappa_3(G) = |F|= min\{|N_G(C_4)|, |N_G(P_4)|, |N_G(S_4)|\}\)</EquationSource> </InlineEquation>. As application, we derive exact values of <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(3\)</EquationSource> </InlineEquation>-extra-connectivity for modified bubble-sort graphs <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(MB_n\)</EquationSource> </InlineEquation>, star graphs <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(CS_n\)</EquationSource> </InlineEquation>, cactus-based graphs <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(CN_{2n+1}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation>-ary <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(n\)</EquationSource> </InlineEquation>-cube <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(Q_n^k\)</EquationSource> </InlineEquation> are <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(4n-9\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(4n-10\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(12n-10\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(8n-9\)</EquationSource> </InlineEquation>, respectively. This work generalizes the study of <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(g\)</EquationSource> </InlineEquation>-extra-connectivity from <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(g\in \{1,2\}\)</EquationSource> </InlineEquation> to <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(g=3\)</EquationSource> </InlineEquation>, extending and unifying earlier work of Gu et al. (Inf. Process Lett. 114:486-491, 2014), Hu et al. (Available at SSRN 5193978), Liu et al. (Theor. Comput. Sci. 888:95-107, 2021) and Zhu et al. (IEEE:1–6, 2017).</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A characterization of 3-extra-cut sets for bipartite hierarchical graph*

  • Wen Zhang,
  • Xiaomin Hu,
  • Shuang Zhao,
  • Weihua Yang

摘要

Connectivity is a classical indicator to reflect the reliability of network. According to the distribution of fault processors, conditional connectivity of network has received wide attention. In this paper, we prove that every minimum 3-extra-cut set \(F\) of \(r\) -regular bipartite hierarchical graph \(G\) is isomorphic to \(N_G(C_4), N_G(P_4)\) or \(N_G(S_4)\) , if for each subgraph \(G_i\) , \(G_i-F_i\) has no isolated vertices, and for a component \(H\) of \(G_1-F_1\) , which is also a component of \(G-F\) , satisfies \(|N_{G_1}(H)| \geq \alpha - 4l - |H| + 4\) and \(|N_{G - G_1}(H)| \geq l|H|\) . It follows that \(3\) -extra-connectivity \(\kappa_3(G) = |F|= min\{|N_G(C_4)|, |N_G(P_4)|, |N_G(S_4)|\}\) . As application, we derive exact values of \(3\) -extra-connectivity for modified bubble-sort graphs \(MB_n\) , star graphs \(CS_n\) , cactus-based graphs \(CN_{2n+1}\) and \(k\) -ary \(n\) -cube \(Q_n^k\) are \(4n-9\) , \(4n-10\) , \(12n-10\) and \(8n-9\) , respectively. This work generalizes the study of \(g\) -extra-connectivity from \(g\in \{1,2\}\) to \(g=3\) , extending and unifying earlier work of Gu et al. (Inf. Process Lett. 114:486-491, 2014), Hu et al. (Available at SSRN 5193978), Liu et al. (Theor. Comput. Sci. 888:95-107, 2021) and Zhu et al. (IEEE:1–6, 2017).