The Conditional-(g, d, k)-Connectivity and Conditional-(g, d, k)-edge-Connectivity on the Hypercubes

• Autorzy: Lin Cheng-Kuan , Ma Liang , Fan Jianxi , Hsu Lih-Hsing , Teng Yuan-Hsiang

Identyfikatory

DOI

10.3233/FI-2020-1914

• Języki publikacji: EN

Abstrakty

EN

We propose two new measures of conditional connectivity to be the extension of R_g-connectivity and R_g-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg_G–F(p) + deg_G–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κ^g,d,k(λ^g,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ^1,1,k, κ^1,d,2, λ^1,1,1 and λ^1,d,2 for the hypercubes.

Słowa kluczowe

EN

conditional connectivity; hypercube

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 173, nr 1
• Strony: 33--45
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Lin Cheng-Kuan

• College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China

autor

Ma Liang

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

autor

Fan Jianxi

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

autor

Hsu Lih-Hsing

• Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.

autor

Teng Yuan-Hsiang

• Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.

Bibliografia

• [1] Abraham S, Padmanabhan K. The twisted cube topology for multiprocessors: a study in networks asymmetry, Parallel and Distributed Computing, 1991;13(1):104-110. URL https://doi.org/10.1016/0743-7315(91)90113-N.
• [2] Chang NW, Hsieh SY. {2, 3}-extraconnectivities of hypercube-like networks, Journal of Computer and System Sciences, 2013;79(5):669-688. URL https://doi.org/10.1016/j.jcss.2013.01.013.
• [3] Chen YC, Tan JJM. Restricted connectivity for three families of interconnection networks, Applied Mathematics and Computation, 2007;188:1848-1855. URL https://doi.org/10.1016/j.amc.2006.11.085.
• [4] Day K, Tripathi A. Unidirectional star graphs, Information Processing Letters, 1993;45:123-129. URL https://doi.org/10.1016/0020-0190(93)90013-Y.
• [5] Efe K. The crossed cube architecture for parallel computation, IEEE Transactions on Parallel and Distributed Systems, 1992;3(5):513-524. URL https://doi.org/10.1109/71.159036.
• [6] Esfahanian AH. Generalized measures of fault tolerance with application to n-cube networks, IEEE Transactions on Computers, 1989;38(11):1586-1591. URL https://doi.org/10.1109/12.42131.
• [7] Esfahanian AH, Hakimi SL. On computing a conditional edge-connectivity of a graph, Information Processing Letters, 1988;27:195-199. URL https://doi.org/10.1016/0020-0190(88)90025-7.
• [8] Fábrega J, Fiol MA. On the extra connectivity of graphs, Discrete Mathematics, 1996;155(13):49-57. URL https://doi.org/10.1016/0012-365X(94)00369-T.
• [9] Harary F. Conditional connecticity, Networks, 1983;13(3):347-357. doi:10.1002/net.3230130303.
• [10] Harary F, Hayes JP, Wu HJ. A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 1988;15:277-289. URL https://doi.org/10.1016/0898-1221(88)90213-1.
• [11] Hong WS, Hsieh SY. Extra edge connectivity of hypercube-like networks, International Journal of Parallel, Emergent and Distributed Systems, 2013;28(2):123-133. URL https://doi.org/10.1080/17445760.2011.650696.
• [12] Hsieh SY, Chang YH. Extraconnectivity of k-ary n-cube networks, Theoretical Computer Science, 2012;443:63-69. URL https://doi.org/10.1016/j.tcs.2012.03.030.
• [13] Hsu LH, Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-13:9781420044812.
• [14] Ju MY, Wang JJ, Chang SH. Diameter variability of hypercubes, Theoretical Computer Science, 2014;542:63-70. URL https://doi.org/10.1016/j.tcs.2014.04.033.
• [15] Lai PL, Tan JJM, Chang C, Hsu LH. Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers, 2005;54(2):165-175. doi:10.1109/TC.2005.19.
• [16] Latifi S, Hegde M, Pour MN. Conditional connectivity measures for large multiprocessor systems, IEEE Transactions on Computers, 1994;43(2):218-222. doi:10.1109/12.262126.
• [17] Li XJ, Xu JM. Edge-fault tolerance of hypercube-like networks, Information Processing Letters, 2013;113:760-763. URL https://doi.org/10.1016/j.ipl.2013.07.010.
• [18] Louri A, Sung HK. An optical multi-mesh hypercube: A scalable optical interconnection network for massively parallel computing, Journal of Lightwave Technology, 1994;12(4):704-716. doi:10.1109/50.285368.
• [19] Pai KJ, Chang JM, Yang JS, Wu RY. Incidence coloring on hypercubes, Theoretical Computer Science, 2014;557:59-65. URL https://doi.org/10.1016/j.tcs.2014.08.017.
• [20] Wang YQ. Super restricted edge-connectivity of vertex-transitive graphs, Discrete Mathematics, 2004;289(1-3):199-205. URL https://doi.org/10.1016/j.disc.2004.08.011.
• [21] Yang WH, Meng JX. Extra connectivity of hypercubes, Applied Mathematics Letters, 2009;22(6):887-891. URL https://doi.org/10.1016/j.aml.2008.07.016.
• [22] Zhu Q, Xu JM, Lv M. Edge fault tolerance analysis of a class of interconnection networks, Applied Mathematics and Computation, 2006;172:111-121. URL https://doi.org/10.1016/j.amc.2005.01.126.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).