Cycle Existence for All Edges in Folded Hypercubes under Scope Faults
The reliability of large-scale networks can be compromised by various factors such as natural disasters, human-induced incidents such as hacker attacks, bomb attacks, or even meteorite impacts, which can lead to failures in scope of processors or links. Therefore, ensuring fault tolerance in the int...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/15/3391 |
| _version_ | 1797586370305196032 |
|---|---|
| author | Che-Nan Kuo Yu-Huei Cheng |
| author_facet | Che-Nan Kuo Yu-Huei Cheng |
| author_sort | Che-Nan Kuo |
| collection | DOAJ |
| description | The reliability of large-scale networks can be compromised by various factors such as natural disasters, human-induced incidents such as hacker attacks, bomb attacks, or even meteorite impacts, which can lead to failures in scope of processors or links. Therefore, ensuring fault tolerance in the interconnection network is vital to maintaining system reliability. The <i>n</i>-dimensional folded hypercube network structure, denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, is constructed by adding an edge between every pair of vertices with complementary addresses from an <i>n</i>-dimensional hypercube, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. Notably, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> exhibits distinct characteristics based on the dimensionality: it is bipartite for odd integers <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> and non-bipartite for even integers <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>. Recently, in terms of the issue of how <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> performs in communication under regional or widespread destruction, we mentioned that in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, even when a pair of adjacent vertices encounter errors, any fault-free edge can still be embedded in cycles of various lengths. Additionally, even when the smallest communication ring experiences errors, it is still possible to embed cycles of any length. The smallest communication ring in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> is observed to be the four-cycle ring. In order to further investigate the communication capabilities of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, we further discuss whether every fault-free edge will still be a part of every communication ring with different lengths when the smallest communication ring is compromised in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. In this study, we consider a fault-free edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>=</mo><mo>(</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub><mo>=</mo><mo>{</mo><msub><mrow><mi>f</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>,</mo><mtext> </mtext><msub><mrow><mi>f</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mn>3</mn></mrow></msub><mo>,</mo><mtext> </mtext><msub><mrow><mi>f</mi></mrow><mrow><mn>4</mn></mrow></msub><mo>}</mo></mrow></semantics></math></inline-formula> as the set of faulty extreme vertices for any four cycles in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. Our research focuses on investigating the cycle-embedding properties in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, where the fault-free edges play a significant role. The following properties are demonstrated: (1) For <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula> in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, every even length cycle with a length ranging from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>4</mn><mo> </mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">o</mi><mo> </mo><msup><mrow><mn>2</mn></mrow><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>4</mn></mrow></semantics></math></inline-formula> contains a fault-free edge <i>e</i>; (2) For every even <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula> in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, every odd length cycle with a length ranging from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>+</mo><mn>1</mn><mtext> </mtext><mi mathvariant="normal">t</mi><mi mathvariant="normal">o</mi><mtext> </mtext><msup><mrow><mn>2</mn></mrow><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>5</mn></mrow></semantics></math></inline-formula> contains a fault-free edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi></mrow></semantics></math></inline-formula>. These findings provide insights into the cycle-embedding capabilities of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, specifically in the context of fault tolerance when considering certain sets of faulty vertices. |
| first_indexed | 2024-03-11T00:22:19Z |
| format | Article |
| id | doaj.art-4a38a14d21bb4e9fbfa5434c16348ee0 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T00:22:19Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-4a38a14d21bb4e9fbfa5434c16348ee02023-11-18T23:16:03ZengMDPI AGMathematics2227-73902023-08-011115339110.3390/math11153391Cycle Existence for All Edges in Folded Hypercubes under Scope FaultsChe-Nan Kuo0Yu-Huei Cheng1Department of Artificial Intelligence, CTBC Financial Management College, Tainan 709, TaiwanDepartment of Information and Communication Engineering, Chaoyang University of Technology, Taichung 413, TaiwanThe reliability of large-scale networks can be compromised by various factors such as natural disasters, human-induced incidents such as hacker attacks, bomb attacks, or even meteorite impacts, which can lead to failures in scope of processors or links. Therefore, ensuring fault tolerance in the interconnection network is vital to maintaining system reliability. The <i>n</i>-dimensional folded hypercube network structure, denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, is constructed by adding an edge between every pair of vertices with complementary addresses from an <i>n</i>-dimensional hypercube, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. Notably, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> exhibits distinct characteristics based on the dimensionality: it is bipartite for odd integers <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> and non-bipartite for even integers <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>. Recently, in terms of the issue of how <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> performs in communication under regional or widespread destruction, we mentioned that in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, even when a pair of adjacent vertices encounter errors, any fault-free edge can still be embedded in cycles of various lengths. Additionally, even when the smallest communication ring experiences errors, it is still possible to embed cycles of any length. The smallest communication ring in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> is observed to be the four-cycle ring. In order to further investigate the communication capabilities of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, we further discuss whether every fault-free edge will still be a part of every communication ring with different lengths when the smallest communication ring is compromised in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. In this study, we consider a fault-free edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>=</mo><mo>(</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub><mo>=</mo><mo>{</mo><msub><mrow><mi>f</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>,</mo><mtext> </mtext><msub><mrow><mi>f</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>,</mo><msub><mrow><mi>f</mi></mrow><mrow><mn>3</mn></mrow></msub><mo>,</mo><mtext> </mtext><msub><mrow><mi>f</mi></mrow><mrow><mn>4</mn></mrow></msub><mo>}</mo></mrow></semantics></math></inline-formula> as the set of faulty extreme vertices for any four cycles in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. Our research focuses on investigating the cycle-embedding properties in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, where the fault-free edges play a significant role. The following properties are demonstrated: (1) For <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula> in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, every even length cycle with a length ranging from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>4</mn><mo> </mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">o</mi><mo> </mo><msup><mrow><mn>2</mn></mrow><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>4</mn></mrow></semantics></math></inline-formula> contains a fault-free edge <i>e</i>; (2) For every even <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula> in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>−</mo><msub><mrow><mi>F</mi></mrow><mrow><mn>4</mn></mrow></msub></mrow></semantics></math></inline-formula>, every odd length cycle with a length ranging from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>+</mo><mn>1</mn><mtext> </mtext><mi mathvariant="normal">t</mi><mi mathvariant="normal">o</mi><mtext> </mtext><msup><mrow><mn>2</mn></mrow><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>5</mn></mrow></semantics></math></inline-formula> contains a fault-free edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi></mrow></semantics></math></inline-formula>. These findings provide insights into the cycle-embedding capabilities of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mi>F</mi><mi>Q</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>, specifically in the context of fault tolerance when considering certain sets of faulty vertices.https://www.mdpi.com/2227-7390/11/15/3391graph theoryinterconnection networksreliabilityscope faultsfolded hypercubes |
| spellingShingle | Che-Nan Kuo Yu-Huei Cheng Cycle Existence for All Edges in Folded Hypercubes under Scope Faults Mathematics graph theory interconnection networks reliability scope faults folded hypercubes |
| title | Cycle Existence for All Edges in Folded Hypercubes under Scope Faults |
| title_full | Cycle Existence for All Edges in Folded Hypercubes under Scope Faults |
| title_fullStr | Cycle Existence for All Edges in Folded Hypercubes under Scope Faults |
| title_full_unstemmed | Cycle Existence for All Edges in Folded Hypercubes under Scope Faults |
| title_short | Cycle Existence for All Edges in Folded Hypercubes under Scope Faults |
| title_sort | cycle existence for all edges in folded hypercubes under scope faults |
| topic | graph theory interconnection networks reliability scope faults folded hypercubes |
| url | https://www.mdpi.com/2227-7390/11/15/3391 |
| work_keys_str_mv | AT chenankuo cycleexistenceforalledgesinfoldedhypercubesunderscopefaults AT yuhueicheng cycleexistenceforalledgesinfoldedhypercubesunderscopefaults |