互連網絡； (r+1)-分量邊連通性； 強門格爾邊連通性； 笛卡爾積圖

高性能計算是通過并行處理和互連技術連接多個計算節點，以快速、可靠、高效地運行高級應用的過程[7]。它可以為標準桌面計算機解決商業、工程或科學領域的復雜問題提供更高的性能，并已成為解決國家安全、經濟發展、科學研究和其它領域許多關鍵問題的重要工具[16]。如今，它已成為解決科學研究和經濟增長眾多重要問題的關鍵工具。在設計構建并行計算機時，使用互連網絡連接所有處理元件至關重要。互連網絡被建模為無向圖G=(V(G), E(G))，其中處理器和通信鏈路分別代表頂點和邊。

關于圖的定義和符號，我們遵循文獻[5]的工作。考慮G是一個無向簡單圖。設X是V(G)的一個子集。我們用Xˉ=V(G)?X表示其補集。X在G中的基數通常表示為|X|。由X誘導的子圖記作G[X]，其頂點集為X，邊集由G中所有端點都在X內的邊組成。對于圖G中的一個頂點u，我們用N_G(u)表示u在G中的所有鄰居，用deg_G(u)表示N_G(u)的基數。對于集合F?E(G)，我們用G?F表示從G中刪除F后得到的圖。對于X,Y?V(G)，我們用[X,Y]_G表示G中一個端點在X、另一個端點在Y的所有邊的集合，即[X,Y]_G={ab∈E(G)∣a∈X, b∈Y}。由任意m個頂點誘導的子圖的最大度和表示為ex_m(G)。設ξ_m(G)=min{|[X,Xˉ]_G|: X?V(G) 滿足 |X|=m≤?|V(G)|/2?， 且G[X]和G[Xˉ]都連通}。

在考慮互連網絡的設計和運行時，可靠性和效率不容忽視。更多的不相交路徑意味著更多的信息傳輸鏈路，這顯著提高了互連網絡的效率。因此，在發生邊故障時，研究互連網絡的邊連通性λ(G)尤其重要。圖G的邊連通性的一個基本定義是(u, v)-路徑的最大邊不相交路徑數集合中的最小值，其中u, v∈V(G)。1984年，Sampathkumar[17]引入了連通圖G的r-分量邊連通性概念，為互連網絡的容錯性提供了一個更精細的參數。如果存在，連通圖G的子集F被稱為G的一個r-分量邊割，如果在G?F中至少有r個連通分量。G的r-分量邊連通性，記作cλ_r(G)，是G的任何r-分量邊割的最小基數。Boesch和Chen[4]研究了r-分量邊連通性的幾個性質，并基于圖G的最小度和度序列建立了其下界。近年來，r-分量邊連通性的概念引起了高度關注。例如，超立方體Q_n[25]，增強立方體AQ_n[23]，BC網絡B_n[12]，3元n-立方體K₃ⁿ[19]，局部扭曲立方體LTQ_n[18]，漢明圖K_Lⁿ[20]等。

眾所周知，λ(G)≤δ(G)，這意味著邊連通性的大小受最小度的限制。隨著互連網絡的擴展，最大度與最小度之間的差異將逐漸擴大，這導致邊連通性無法很好地反映度數較大頂點的連通性。2003年，Oh等人[14]提出了強門格爾邊連通性的概念：如果對于圖G中的每對頂點u和v，在u和v之間存在min{deg_G(u), deg_G(v)}條不相交路徑，則稱連通圖G為強門格爾邊連通的（簡稱SM-λ）。評估網絡的容錯性至關重要，因為實際網絡中可能存在故障。2018年，Cheng等人[6]為帶有故障的圖引入了強門格爾邊連通性的定義。如果對于任意邊集F?E(G)且|F|≤m，G?F保留SM-λ性質，則稱圖G是m-邊故障容忍強門格爾連通的。如果故障數量不是過多，假設它們均勻隨機分布，則每條故障邊關聯到單個頂點的可能性不大。基于這些原因，2018年，He等人[8]提出了m-階t強門格爾邊連通性的定義以及最大整數m，記作sm_λ^t(G)。給定一個固定整數t，令F是連通圖G的一個滿足限制條件δ(G?F)≥t的邊集。那么邊集F是一個t階條件故障邊集。如果圖G中的每一對頂點u和v在G?F中都由min{deg_G?F(u), deg_G?F(v)}條邊不相交的路徑連接，則圖G被稱為是F-強門格爾邊連通的（簡稱F-SMEC）且階為t。如果對于每個滿足|F|≤m且F是t階條件邊故障集的F，圖G是F-SMEC且階為t，則稱圖G是m-階t強門格爾邊連通的。

F-強門格爾邊連通性已被多位研究者用于研究多種互連網絡，如下所示：對于Q_n，Qiao和Yang[15]證明了對于n≥4，有sm_λ²(Q_n)=(2n?4)；對于平衡超立方體BH_n，Li和Xu[11]證明了對于n≥2，有sm_λ²(BH_n)=(6n?8)；對于B_n，Liu等人[13]得到了對于n≥3且1≤t≤n?2，有sm_λ^t(B_n)=2^t(n?t)?n；對于折疊超立方體FQ_n，Zhao和Li[24]證明了對于1≤t≤n?2且n≥4，有sm_λ^t(FQ_n)=2^t(n?t+1)?(n+1)；最近，Zhang等人[22]證明了對于1≤t≤n?2且n≥3，有sm_λ^(L?1)t(K_Lⁿ)=L^t(n?t)(L?1)?(L?1)n；對于完全約瑟夫立方體CJC_n，Huang等人[9]確定了對于4≤t≤n?2且n≥6，有sm_λ^t(CJC_n)=2^t(n?t+1)?(n+2)。

笛卡爾積冪圖(K₉?C₉)ⁿ作為一種新型互連網絡，在研究領域引起了廣泛關注。2018年，Bezrukov等人[3]利用詞典序找到了笛卡爾積冪圖(K₉?C₉)ⁿ邊等周問題的最優解。2021年，Afiya和Rajesh[1]探索了(K₉?C₉)ⁿ的泛環性。2023年，Afiya和Rajesh[2]確定了將(K₉?C₉)ⁿ嵌入大小為9ⁿ的路徑、香蕉樹和鞭炮樹的最優線長。本文重點關注笛卡爾積冪圖(K₉?C₉)ⁿ的兩個參數：(r+1)-分量邊連通性cλ_r+1((K₉?C₉)ⁿ)和6t階的F-強門格爾邊連通性，記作sm_λ^6t((K₉?C₉)ⁿ)。我們證明了對于0≤t≤n?2且n≥3，有sm_λ^6t((K₉?C₉)ⁿ)=6(n?t)9^t?6n。此外，我們還證明了對于r≤9^?n/2?且n≥4，有cλ_r+1((K₉?C₉)ⁿ)=6nr?ex_r((K₉?C₉)ⁿ)/2。

論文的其余部分組織如下。在第2節中，我們闡述了笛卡爾積冪圖(K₉?C₉)ⁿ的一些基本結構。在第3節中，我們分析了(K₉?C₉)ⁿ的邊等周問題相關函數ξ_m((K₉?C₉)ⁿ)的層次單調性和迭代性，以及函數ex_m((K₉?C₉)ⁿ)的一些性質。在第4節中，我們確立了(K₉?C₉)ⁿ的6t階F-強門格爾邊連通性的精確值。