Journal
COMPUTER JOURNAL
Volume 64, Issue 5, Pages 812-825Publisher
OXFORD UNIV PRESS
DOI: 10.1093/comjnl/bxaa037
Keywords
Strong Menger edge connectivity; maximal local-connectivity; augmented k-ary n-cubes; fault-tolerance
Categories
Funding
- China Postdoctoral Science Foundation [2018M631322]
- Czech Operational Programme Research, Development and Education (OP RDE) [CZ.02.2.69/0.0/0.0/16-027/0008495]
- International Mobility of Researchers at Charles University
- Ministry of Science and Technology, Taiwan [107-2221-E-141-001-MY3]
- National Natural Science Foundation of China [11971054, 11731002]
Ask authors/readers for more resources
This paper examines the strong Menger (edge) connectedness properties of graphs, exploring the topological features of the augmented k-ary n-cube. The results show that under certain conditions, specific graphs exhibit optimal connectivity, tolerating the maximum number of faults.
A connected graph G is called strongly Menger (edge) connected if for any two distinct vertices x, y of G, there are min{deg(G)(x), deg(G)(y)} internally disjoint (edge disjoint) paths between x and y. Motivated by parallel routing in networks with faults, Oh and Chen (resp., Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph G is called m-strongly Menger (edge) connected if G- F remains strongly Menger (edge) connected for an arbitrary vertex set F subset of V(G) (resp. edge set F subset of E(G)) with vertical bar F vertical bar <= m. A graph G is called m-conditional strongly Menger (edge) connected if G- F remains strongly Menger (edge) connected for an arbitrary vertex set F subset of V(G) (resp. edge set F subset of E(G)) with vertical bar F vertical bar <= m and delta(G - F) >= 2. In this paper, we consider strong Menger (edge) connectedness of the augmented k-ary n-cube AQ(n,k), which is a variant of k-ary n-cube Q(n)(k). By exploring the topological proprieties of AQ(n,k), we show that AQ(n,3) (resp. AQ(n,k), k >= 4) is (4n - 9)-strongly (resp. (4n - 8)-strongly) Menger connected for n >= 4 (resp. n >= 2) and AQ(n,k) is (4n - 4)-strongly Menger edge connected for n >= 2 and k >= 3. Moreover, we obtain that AQ(n,k) is (8n - 10)-conditional strongly Menger edge connected for n >= 2 and k >= 3. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available