Link fault tolerability of the Cartesian product power graph $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n: conditional edge-connectivities under six link fault patterns

Zhaoman Huang (), Yayu Yang (), Mingzu Zhang () and Weihua Yang ()
Additional contact information
Zhaoman Huang: Xinjiang University
Yayu Yang: Xinjiang University
Mingzu Zhang: Xinjiang University
Weihua Yang: Taiyuan University of Technology

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 15, 20 pages

Abstract: Abstract High-performance computing extensively depends on parallel and distributed systems, necessitating the establishment of quantitative parameters to evaluate the fault tolerability of interconnection networks. The topological structures of interconnection networks in some parallel and distributed systems are designed as n-dimensional $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n , obtained through the repeatedly application of the n-th Cartesian product operation. Since the $$\mathcal {P}$$ P -conditional edge-connectivity is proposed by Harary, as a parameter for evaluating the link fault tolerability of the underlying topology graph of the interconnection network system, it has been widely studied in many interconnection networks. The $$\mathcal {P}$$ P -conditional edge-connectivity of a connected graph G, denoted by $$\lambda (\mathcal {P};G)$$ λ ( P ; G ) , if any, describes the minimum cardinality of the fault edge-cut of the graph G, whose malfunction divides G into multiple components, with each component satisfying a given property $$\mathcal {P}$$ P of the graph. In this paper, we primarily define $$\mathcal {P}_{i}^{t}$$ P i t to be properties of containing at least $$9^t$$ 9 t processors, every remaining processor lying in a lower dimensional subnetwork of the $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n , $$(K_{9}-C_{9})^{t}$$ ( K 9 - C 9 ) t , having a minimum degree or average degree of at least 6t, existing two components with each component having at least $$9^t$$ 9 t processors, and containing at least one cycle, respectively. We use the properties of the optimal solution to the edge isoperimetric problem of $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n and find that the exact values of the $$\mathcal {P}_{i}$$ P i -conditional edge-connectivities of the graph $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n share a common value of $$6(n-t)9^t$$ 6 ( n - t ) 9 t for $$1\le i\le 5$$ 1 ≤ i ≤ 5 and $$0\le t\le n-1$$ 0 ≤ t ≤ n - 1 , except for $$i=6$$ i = 6 , the value is $$18n - 6$$ 18 n - 6 .

Keywords: Link fault tolerability; Interconnection networks; High-performance computing; $$\mathcal {P}$$ P -Conditional; $$(K_{9}-C_{9})^{n}$$ ( K 9 - C 9 ) n (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01273-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01273-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01273-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().